Skip to content

Instantly share code, notes, and snippets.

@hkasera
Created March 17, 2017 22:25
Show Gist options
  • Save hkasera/0cdcaa8607fbed89cc01d845b7405ebd to your computer and use it in GitHub Desktop.
Save hkasera/0cdcaa8607fbed89cc01d845b7405ebd to your computer and use it in GitHub Desktop.
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int[] sum = new int[nums.length];
int[] indices = new int[nums.length];
sum[0] = nums[0];
indices[0] = 0;
for(int i = 1 ; i < nums.length ; ++i){
if(sum[i-1]+nums[i] >= nums[i]){
sum[i] = sum[i-1]+nums[i];
}else{
sum[i] = nums[i];
indices[i] = i;
}
}
int maxSum = sum[0];
int index = 0;
for(int j = 1 ; j < sum.length ; ++j){
if(sum[j] >= maxSum){
maxSum = sum[j];
index = j;
}
}
return maxSum;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment