C++ O(n) time O(n) space concise solution


  • 3
    E

    Let b[i] be contiguous sum of k elements ending with index i. We need to find the max sum of b[x] + b[y] + b[z] where x + 2k <= y + k <= z. We traverse the array, store solutions for cases of 1 sum (delayed by 2*k steps) , 2 sums (delayed by k steps), 3 sums (no delay) and update those each time we visit new element.

    class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& a, int k) {
            int n = a.size();
            vector<int> c[3], m(3); //store optimal solutions for 1 sum, 2 sums, 3 sums.
            vector<int> b(n);
            int sm = 0;
            for (int i = 0; i < n; ++i) {
                sm += a[i];
                if (i >=k-1) {
                    b[i] = sm;
                    sm -= a[i-k+1];
                    if (i >= 3 * k-1) {
                        if (b[i-k-k] > m[0]) { // update 1 sum solution
                            m[0] = b[i-k-k];
                            c[0] = {i-k-k};
                        }
                        if (b[i-k] + m[0] > m[1]) { // update 2 sums solution
                            m[1] = b[i-k] + m[0];
                            c[1] = {c[0][0], i-k};
                        }
                        if (b[i] + m[1] > m[2]) { //update 3 sums solution
                            m[2] = m[1] + b[i];
                            c[2] = {c[1][0], c[1][1], i};
                        }
                    }
                }
            }
            
            return {c[2][0]-k + 1,c[2][1]-k+1,c[2][2]-k+1};
        }
    };
    

  • 0
    Q

    @dickchimney Thanks for sharing. Great solution.


  • 2
    E

    @QQBear You're welcome.


Log in to reply
 

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