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

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

Understanding the Problem

The core challenge of this problem is to find three non-overlapping subarrays that together yield the maximum possible sum. This problem is significant in scenarios where we need to maximize profit or minimize cost over multiple non-overlapping intervals, such as in financial analysis or resource allocation.

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

Approach

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

Calculate the sum of all possible subarrays of a given length.
Use dynamic programming to keep track of the maximum sum of subarrays ending at or starting from each index.
Combine these 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, which would be computationally expensive and inefficient (O(n^3) time complexity). This is not optimal for large arrays.

Optimized Solution

We can optimize the solution using dynamic programming and prefix sums. The idea is to precompute the sums of all subarrays of a given length and then use these precomputed sums to find the maximum sum of three non-overlapping subarrays efficiently.

Algorithm

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

Compute the prefix sums of the array to quickly calculate subarray sums.
Use dynamic programming to find the maximum sum of subarrays ending at each index.
Use dynamic programming to find the maximum sum of subarrays starting from each index.
Combine the results to find the maximum sum of three non-overlapping subarrays.

Code Implementation


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

using namespace std;

// Function to find the maximum sum of three non-overlapping subarrays
int maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> sum(n + 1, 0); // Prefix sums
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + nums[i];
    }

    vector<int> left(n, 0); // Max sum of subarray ending at or before each index
    vector<int> right(n, 0); // Max sum of subarray starting at or after each index

    // Calculate left max subarray sums
    int maxSum = sum[k] - sum[0];
    for (int i = k; i < n; ++i) {
        if (sum[i + 1] - sum[i + 1 - k] > maxSum) {
            maxSum = sum[i + 1] - sum[i + 1 - k];
            left[i] = i + 1 - k;
        } else {
            left[i] = left[i - 1];
        }
    }

    // Calculate right max subarray sums
    maxSum = sum[n] - sum[n - k];
    right[n - k] = n - k;
    for (int i = n - k - 1; i >= 0; --i) {
        if (sum[i + k] - sum[i] >= maxSum) {
            maxSum = sum[i + k] - sum[i];
            right[i] = i;
        } else {
            right[i] = right[i + 1];
        }
    }

    // Find the maximum sum by combining left, middle, and right subarrays
    int result = 0;
    for (int i = k; i <= n - 2 * k; ++i) {
        int l = left[i - 1];
        int r = right[i + k];
        int total = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);
        result = max(result, total);
    }

    return result;
}

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

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input array. This is because we make a constant number of passes over the array to compute prefix sums and dynamic programming arrays. The space complexity is also O(n) due to the additional arrays used for prefix sums and dynamic programming.

Edge Cases

Potential edge cases include:

Arrays with negative numbers.
Arrays where the optimal subarrays are at the beginning or end of the array.
Arrays with all positive or all negative numbers.

Each of these cases is handled by the algorithm as it considers all possible subarrays and uses dynamic programming to ensure optimal results.

Testing

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

Simple cases with small arrays.
Cases with mixed positive and negative numbers.
Cases with all positive or all negative numbers.
Edge cases with subarrays at the boundaries of the array.

Using a testing framework like Google Test can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider breaking them down into smaller subproblems and using dynamic programming to optimize the solution. Practice solving similar problems and study common algorithms to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the problem of finding the maximum sum of three non-overlapping subarrays using dynamic programming and prefix sums. We provided a detailed explanation of the algorithm, code implementation, and complexity analysis. Understanding and solving such problems is crucial for developing strong problem-solving skills in competitive programming and real-world applications.

Additional Resources

For further reading and practice, consider the following resources: