The problem
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
The code
// This method takes an array of `ints` and returns an `int`
public int maxSubArray(int[] nums) {
// Set some `max` variables,
// ..firstly the minimum `Integer` value
// ..secondly `0`
int max = Integer.MIN_VALUE;
int iMax = 0;
// Loop through all input `nums`
for(int num : nums) {
// increment the `iMax` each loop
iMax = iMax + num;
// check if `num` is bigger than `iMax`
if(iMax < num) {
// set `iMax` to the `num`
iMax = num;
}
// set the `max` to the max of both our variables
max = Math.max(max,iMax);
}
// return the `max`
return max;
}