DP求解


  • 0
    X
    class Solution {
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        
        // sum[i]保存第i个元素之前的所有元素的和,不包括i。leftindex[i]保存了[0, i]中最大的左子序列的startindex。rightindex为右。
        vector<int> sum(1, 0), leftindex(n, 0), rightindex(n, n-k), ans(3, 0);
        
        for (int i: nums)
            sum.push_back(sum.back() + i);
        
        for (int i = k, max = sum[k] - sum[0]; i < n; ++i) {
            if (sum[i+1] - sum[i-k+1] > max) {  // 因为leftindex保存的是[0,i]之间的最大左子序列start,所以要+1。下边rightindex因为是[i,n-1]所以不用+1
                leftindex[i] = i - k + 1;
                max = sum[i+1] - sum[i-k+1];
            } else {
                leftindex[i] = leftindex[i-1];
            }
        }
        
        for (int i = n-k-1, max = sum[n] - sum[n-k]; i >= 0; --i) {
            if (sum[i+k] - sum[i] >= max) {  // 注意这里的等号(因为i是递减的,所以后续迭代有等于max也要更新)
                rightindex[i] = i;
                max = sum[i+k] - sum[i];
            } else {
                rightindex[i] = rightindex[i+1];
            }
        }
        
        for (int i = k, max = 0; i <= n - 2 * k; i++) {  // 注意条件的等号
            int j = sum[leftindex[i-1]+k] - sum[leftindex[i-1]] + sum[i+k] - sum[i] + sum[rightindex[i+k]+k] - sum[rightindex[i+k]];
            if (j > max) {
                max = j;
                ans[0] = leftindex[i-1];
                ans[1] = i;
                ans[2] = rightindex[i+k];
            }
        }
        
        return ans;
    }
    };
    
    /*
        DP思想,定义了F(i)为中间序列的首元素为i时的最大和。前面的三个for循环也是dp,J(i)为从0到i中的最大和。
    */

Log in to reply
 

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