Description

Submission

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 0);

        vector<int> presum(n+1);
        presum[0] = 0;

        for(int i = 1; i <= n; ++i) {
            presum[i] = presum[i-1] + nums[i];
        }

        vector<int> largest(n+1);
        largest[n] = presum[n];

        for(int i = n-1; i >= 0; --i) {
            largest[i] = max(largest[i+1], presum[i]);
        }

        int ret = INT_MIN;
        for(int i = 0; i < n; ++i) {
            ret = max(ret, largest[i+1] - presum[i]);
        }
        return ret;
    }
};

// 0,-2,1,-3,4,-1,2,1,-5,4
// 0,-2,-1,-4,0,-1,1,2,-3,1