Maximum Sum of 3 Non-Overlapping Subarrays

Leetcode Problem:

• Maximum Sum of 3 Non-Overlapping Subarrays

Summary

• Given an integer array and an integer k, find three non-overlapping subarrays of length k with maximum sum and return their starting indices.

Approach

• Dynamic programming and depth-first search are used to find the maximum possible sum of subarrays and then reconstruct the path to find the starting indices.

Complexity

• O(n * 4^k) where n is the size of the input array, as the dynamic programming function is called for each possible subarray and for each possible number of subarrays remaining.

Explanation

• The solution first calculates the sum of all possible k-length subarrays using a sliding window approach
• Then, it uses dynamic programming to find the maximum possible sum of subarrays
• The dynamic programming function tries taking the current subarray vs skipping it and returns the maximum result
• Finally, the solution uses depth-first search to reconstruct the path to find the starting indices of the subarrays.

Solution Code:

class Solution {
public:
    vector maxSumOfThreeSubarrays(vector& nums, int k) {
        // Number of possible subarray starting positions
        int n = nums.size() - k + 1;

        // Calculate sum of all possible k-length subarrays
        vector sums(n);
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;

        // Sliding window to calculate remaining sums
        for (int i = k; i < nums.size(); i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            sums[i - k + 1] = windowSum;
        }

        // memo[i][j]: max sum possible starting from index i with j subarrays
        // remaining
        vector> memo(n, vector(4, -1));
        vector indices;

        // First find optimal sum using DP
        dp(sums, k, 0, 3, memo);

        // Then reconstruct the path to find indices
        dfs(sums, k, 0, 3, memo, indices);

        return indices;
    }

private:
    // DP function to find maximum possible sum
    int dp(vector& sums, int k, int idx, int rem,
           vector>& memo) {
        if (rem == 0) return 0;
        if (idx >= sums.size()) {
            return rem > 0 ? INT_MIN : 0;
        }

        if (memo[idx][rem] != -1) {
            return memo[idx][rem];
        }

        // Try taking current subarray vs skipping it
        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        memo[idx][rem] = max(withCurrent, skipCurrent);
        return memo[idx][rem];
    }

    // DFS to reconstruct the solution path
    void dfs(vector& sums, int k, int idx, int rem,
             vector>& memo, vector& indices) {
        if (rem == 0) return;
        if (idx >= sums.size()) return;

        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        // Choose path that gave optimal result in DP
        if (withCurrent >= skipCurrent) {  // Take current subarray
            indices.push_back(idx);
            dfs(sums, k, idx + k, rem - 1, memo, indices);
        } else {  // Skip current subarray
            dfs(sums, k, idx + 1, rem, memo, indices);
        }
    }
};