53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

• prefix sum solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int mi = 0, res = INT_MIN, sum = 0;
        for(auto& n : nums) {
            sum += n;
            res = max(res, sum - mi);
            mi = min(mi, sum);
        }

        return res;
    }
};

• dp solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curMax = 0, maxSum = INT_MIN;
        for(auto& n : nums) {
            curMax = max(curMax + n, n);
            maxSum = max(maxSum, curMax);
        }

        return maxSum;
    }
};