Maximum Subarray Sum
Find the maximum subarray sum in an integer array.
Input: nums = [-3,-4,-1,-2]
Output: -1
Explanation: Kadane's algorithm correctly identifies that the single isolated element -1 provides the highest possible sum.

Question

Find the maximum subarray sum in an integer array.

Input: nums = [-3,-4,-1,-2]

Output: -1

Explanation: Kadane's algorithm correctly identifies that the single isolated element -1 provides the highest possible sum.

Anonymous · Accepted Answer

public int maxSubArray(int[] nums) {

if (nums == null || nums.length == 0) {

return 0;

}

int n = nums.length;

int dp = nums[0];

int max = dp;

for (int i = 1; i < n; i++) {

dp = Math.max(dp + nums[i], nums[i]);

max = Math.max(dp, max);

}

return max;

}