PROBLEM DESCRIPTION
Given an integer array nums, find the subarray with the largest sum, and return its sum.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for(int i=1; i<nums.length; i++){
//the current number may be more than the previous number plus current number, if the previous sum was negative
currentSum = Math.max(currentSum+nums[i], nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}