Leetcode #53: Maximum Subarray

Leetcode_0053.cpp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {      
        int n = nums.size();
        if (n==0) {
            return 0;
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        for (int i=1; i<n; i++) {
            dp[i] = nums[i] + max(0, dp[i-1]);
        }
        return *max_element(dp.begin(), dp.end()); // max in the dp vector.
    }
};
// You can easily reduce the space complexity by using 1-2 variables instead of an entire vector/array.