53. Maximum Subarray

• Visit Leetcode problem

Problem

Given an integer array nums, find the 
subarray with the largest sum, and return its sum.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104

Approach

Implementation

class Solution {
    public int maxSubArray(int[] nums) {
        return kadane(nums);
    }

    private int kadane(int[] nums) {
        int maxSum = nums[0];
        int curSum = 0;

        for (int num : nums) {
            curSum += num;

            if (curSum > maxSum) {
                maxSum = curSum;
            }

            if (curSum < 0) {
                curSum = 0;
            }
        } 

        return maxSum;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[int(1e5 + 1)] = {0};
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};