leetcode-53

53. Maximum Subarray

Leetcode 53

I solved this problem using C++.
My idea: use dynamic programming.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int> &nums)
    {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.size(); ++i)
        {
            currentSum = max(nums[i], currentSum + nums[i]);
            maxSum = max(maxSum, currentSum);
        }

        return maxSum;
    }
};

use currentSum to store the max subarray sum with the current index.
use maxSum to store the max subarray sum of all indices.
currentSum is updated by max(nums[i], currentSum + nums[i]).
maxSum is updated by max(maxSum, currentSum).