Short C++ DP solution O(n), can be generalized to M subarrays


  • 0
    F
    class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
            int n = nums.size();
            vector<vector<int>> v(3, vector<int>(n, 0));
            vector<vector<int>> p(3, vector<int>(n, 0));
            vector<int> sums(n, 0), ans(3, 0);
            
            for (int i = 0; i < n; ++i) sums[i] = nums[i] + (i == 0 ? 0 : sums[i-1]);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (i < (j+1) * k - 1) continue;
                    v[j][i] = sums[i] - (i < k ? 0 : sums[i-k]) + (j == 0 ? 0 : v[j-1][i-k]);
                    if (v[j][i] > v[j][i-1]) {
                        p[j][i] = i - k + 1;
                        if (j == 2) {
                            ans[2] = p[2][i];
                            ans[1] = p[1][ans[2]-1];
                            ans[0] = p[0][ans[1]-1];
                        }
                    } else v[j][i] = v[j][i-1], p[j][i] = p[j][i-1];
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.