We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Attention ! One correction needs to be made for this wiki solution when array has negative value, max_ending_here must be initialized to 0, while max_so_far must be initialized to either Integer.MIN_VALUE or arr[0], instead of 0, in order to handle negative values for calculating max continuous subarray.
ps. I just corrected wiki solution.
My working solution in java:
static void printMaxSum(int[] arr){
//1) For max continuous sub array
int max_ending_here = 0;
int max_so_far = Integer.MIN_VALUE;
/*OR int max_so_far = arr[0];*/
for(int x : arr){
max_ending_here = Math.max(x, max_ending_here + x);
max_so_far = Math.max(max_so_far, max_ending_here);
}
System.out.print(max_so_far);
//2) For max non-continuous sub array, order doesn't matter
Arrays.sort(arr);
int sum = 0;
//if there is none positive value in entire array
if(arr[arr.length-1] <= 0)
sum = arr[arr.length - 1];
//accumulate all positive values in entire array
else{
for(int x : arr){
if(x > 0)
sum += x;
}
}
System.out.println(" " + sum);
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Maximum Subarray
You are viewing a single comment's thread. Return to all comments →
Attention ! One correction needs to be made for this wiki solution when array has negative value, max_ending_here must be initialized to 0, while max_so_far must be initialized to either Integer.MIN_VALUE or arr[0], instead of 0, in order to handle negative values for calculating max continuous subarray.
ps. I just corrected wiki solution.
My working solution in java: