Start learning free

LESSON 240 OF 409 · PARTIAL SUMS #2

Maximum Sum of Three Non-Overlapping Subarrays IV in C++ (Time Complexity: O(n))

Practice O(n) Read the full explanation

Given an array nums of integers, find three non-overlapping subarrays with maximum sum.

Return the total sum of the three subarrays

Example:

Input: [2, 3, -8, 7, -2, 9, -9, 7, -2, 4]
Output: 28
Explanation: Subarrays [2, 3], [7, -2, 9] and [7, -2, 4]
             have the maximum sum of 28

 

Note:

  • Subarrays must be non-empty
  • nums contains at least three numbers
STEP 1 OF 21
    Ctrl + Enter to check

    C++ · PARTIAL SUMS #2

    Max Sum Of Three Subarrays in C++, explained

    Understanding the Problem

    The core challenge of this problem is to find three non-overlapping subarrays that together have the maximum possible sum. This problem is significant in scenarios where we need to maximize the sum of multiple segments of data, such as in financial analysis or signal processing.

    Potential pitfalls include overlapping subarrays and not considering all possible subarray combinations.

    Approach

    To solve this problem, we can break it down into manageable steps:

    1. Calculate the sum of all possible subarrays of a given length.
    2. Use dynamic programming to keep track of the maximum sum of subarrays ending at or before each index.
    3. Combine the results to find the maximum sum of three non-overlapping subarrays.

    Naive Solution

    A naive solution would involve checking all possible combinations of three subarrays, but this approach is not optimal due to its high time complexity.

    Optimized Solution

    We can optimize the solution using dynamic programming:

    1. Calculate prefix sums to quickly get the sum of any subarray.
    2. Use three arrays to store the maximum sum of subarrays ending at or before each index for the first, second, and third subarrays.
    3. Iterate through the array to update these arrays and find the maximum sum of three non-overlapping subarrays.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Calculate the prefix sums of the array.
    2. Initialize three arrays to store the maximum sum of subarrays ending at or before each index for the first, second, and third subarrays.
    3. Iterate through the array to update these arrays based on the prefix sums.
    4. Find the maximum sum of three non-overlapping subarrays by combining the results from the three arrays.

    Code Implementation

    #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to calculate the maximum sum of three non-overlapping subarrays
int maxSumOfThreeSubarrays(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefixSum(n + 1, 0);

    // Calculate prefix sums
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // Arrays to store the maximum sum of subarrays
    vector<int> leftMax(n, 0), rightMax(n, 0);
    int maxSum = INT_MIN;

    // Calculate the maximum sum of subarrays ending at or before each index
    for (int i = 0; i < n; ++i) {
        if (i >= 2) {
            leftMax[i] = max(leftMax[i - 1], prefixSum[i + 1] - prefixSum[i - 2]);
        } else {
            leftMax[i] = prefixSum[i + 1];
        }
    }

    // Calculate the maximum sum of subarrays starting at or after each index
    for (int i = n - 1; i >= 0; --i) {
        if (i <= n - 3) {
            rightMax[i] = max(rightMax[i + 1], prefixSum[i + 3] - prefixSum[i]);
        } else {
            rightMax[i] = prefixSum[n] - prefixSum[i];
        }
    }

    // Find the maximum sum of three non-overlapping subarrays
    for (int i = 2; i < n - 2; ++i) {
        maxSum = max(maxSum, leftMax[i - 1] + (prefixSum[i + 2] - prefixSum[i]) + rightMax[i + 2]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {2, 3, -8, 7, -2, 9, -9, 7, -2, 4};
    cout << "Maximum sum of three non-overlapping subarrays: " << maxSumOfThreeSubarrays(nums) << endl;
    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(n) because we iterate through the array a constant number of times. The space complexity is also O(n) due to the additional arrays used for prefix sums and maximum sums.

    Edge Cases

    Potential edge cases include:

    • Arrays with all negative numbers.
    • Arrays with all positive numbers.
    • Arrays with a mix of positive and negative numbers.

    Each algorithm handles these cases by correctly calculating the prefix sums and updating the maximum sums accordingly.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small arrays.
    • Cases with large arrays to test performance.
    • Edge cases with all negative or all positive numbers.

    Use testing frameworks like Google Test for automated testing.

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Break down the problem into smaller, manageable parts.
    • Consider using dynamic programming to optimize the solution.
    • Practice solving similar problems to improve problem-solving skills.

    Conclusion

    Understanding and solving problems like this one is crucial for developing strong problem-solving skills. Practice regularly and explore different approaches to enhance your understanding.

    Additional Resources

    For further reading and practice:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free