Python Coding Test Course, Finding Continuous Sum

Hello! In this lecture, we will cover one of the algorithm problems using Python, Finding the Maximum Sum of Continuous Elements. This problem can be approached in various ways and is very useful for studying algorithms. We will explain the necessary basic theories and the solution process in detail.

Problem Description

Given an integer array arr, write an algorithm to maximize the sum of k continuous elements within this array. The length of the array is given as n, and k is an integer from 1 to n, inclusive. In other words, we need to calculate the sum of k continuous elements in the array and return the maximum value of this sum.

Input

  • The first line contains the size of the array n (1 ≤ n ≤ 100,000)
  • The second line contains the array arr consisting of n integers (-109 ≤ arri ≤ 109)
  • The third line contains k (1 ≤ k ≤ n)

Output

Output the maximum sum of k continuous elements.

Example Input

5
1 2 3 4 5
3

Example Output

12

Explanation

If we calculate the sum of 3 continuous elements in the given array, the largest value is 3+4+5=12.

Solution Process

To solve this problem, we need an algorithm that can calculate continuous sums. If we simply iterate through the array and sum all k continuous elements to find the maximum, the time complexity would be O(n*k), which is not feasible if n is 100,000. Therefore, we need to solve it in a more efficient way.

Sliding Window Technique

One useful technique to solve this problem is the Sliding Window. The sliding window is a method to quickly calculate a continuous subarray of a specific size within a given array or list. By using this technique, we can reduce the time complexity to O(n).

Algorithm Explanation

  1. Initially, sum the first k elements and set it as the current maximum sum.
  2. Then, focus on the k elements by removing one element and adding a newly added element to update the sum.
  3. Repeat this process until the end of the array to update the maximum sum.

Implementation Code

Now, let’s implement this algorithm in Python. Here is an implementation using the sliding window:

def max_sum_k_elements(n, arr, k):
    # Initial window sum
    current_sum = sum(arr[:k])
    max_sum = current_sum

    # Use sliding window to explore the rest of the elements
    for i in range(k, n):
        current_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, current_sum)

    return max_sum

# Input handling
n = int(input())
arr = list(map(int, input().split()))
k = int(input())

# Output the maximum continuous sum
print(max_sum_k_elements(n, arr, k))

Code Explanation

Let’s take a detailed look at each part of the code:

  • def max_sum_k_elements(n, arr, k): – Function declaration that uses the input array and k to calculate the maximum sum.
  • current_sum = sum(arr[:k]) – Calculates the sum of the initial window.
  • max_sum = current_sum – Initializes the current maximum sum.
  • for i in range(k, n): – Loops from k to n for the sliding window.
  • current_sum += arr[i] - arr[i - k] – Includes the new element and subtracts the excluded element to update the current sum.
  • max_sum = max(max_sum, current_sum) – Updates the maximum sum.
  • return max_sum – Returns the final maximum sum.

Conclusion

We have now solved the problem of maximizing the sum of k continuous elements in an array. By using the sliding window technique, we effectively reduced the time complexity, which is very useful in actual job coding tests.

Additionally, this problem can be modified in other forms, so I recommend practicing with various examples.