C++ Coding Test Course, Finding the Continuous Sum

Problem Description

The problem of calculating the sum of continuous subsequences in an array is a common topic in many coding tests. These problems are a good way to test the ability to manage control flow, manipulate arrays, and consider time complexity. In this tutorial, we will explore this topic in depth through the problem of ‘Calculating Continuous Sums’.

Problem Definition

Write a function to calculate the sum of k continuous elements from the given integer array arr. If the length of arr is n, k must be a value between 1 and n. Here, the user should use an optimized method to calculate the continuous sum, and using simple loops is not recommended.

Input

• The first line contains the integers n (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ n).
• The second line contains an array arr consisting of n integers.

Output

Print the maximum sum of k continuous elements.

Example

    Input:
    5 3
    1 2 3 4 5

    Output:
    12
    

Explanation: The continuous 3 elements are (3, 4, 5) whose total sum is 12.

Problem Solving Process

To solve this problem, there are two main approaches: calculating all combinations using simple iteration and an optimized approach using the sliding window technique.

1. Simple Iteration Method

While it is possible to calculate the sum of k continuous elements using a simple iteration method, this approach has a time complexity of O(n*k) and becomes inefficient as the size of the array increases.

    void simpleSum(int arr[], int n, int k) {
        int maxSum = 0;
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            for (int j = 0; j < k; j++) {
                currentSum += arr[i + j];
            }
            maxSum = max(maxSum, currentSum);
        }
        cout << maxSum << endl;
    }
    

2. Sliding Window Technique

The sliding window technique works by maintaining the sum of k elements by subtracting the previous value and adding the new value. This approach can reduce the time complexity to O(n).

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // Calculate the sum of the first k elements
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // Calculate the sum through the sliding window
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }
    

Code Implementation

Among the two methods above, we will choose the sliding window technique as it is more efficient and write the entire code.

    #include 
    #include 
    using namespace std;

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // Calculate the sum of the first k elements
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // Calculate the sum through the sliding window
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }

    int main() {
        int n, k;
        cin >> n >> k;
        int arr[n];
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        slidingWindowSum(arr, n, k);
        return 0;
    }
    

Conclusion

In this tutorial, we examined how to calculate the sum of continuous subsequences in an array through the problem of 'Calculating Continuous Sums'. By using the sliding window technique, we can reduce the time complexity to O(n), allowing for a more efficient preparation for coding tests.

References

- Basic concepts for solving algorithm problems
- Utilizing C++ STL
- Code optimization and testing patterns