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.
/* The key to this one is that you want to do one pass through the data. I first did a substring inner loop for the max subarray sum (code in comments), but this timed out for one test. int subArraySum = 0; for (int j = i; j < arr.size(); j++) { subArraySum += arr.get(j); if (greatestSum == null || subArraySum > greatestSum) { greatestSum = subArraySum; } } } results.add(greatestSum); */publicstaticList<Integer>maxSubarray2(List<Integer>arr){List<Integer>results=newArrayList<Integer>();intsubArraySum=0;intsumSubSequence=0;intsubArraySumMax=0;for(inti=0;i<arr.size();i++){//this is to get the max subarray sumsubArraySum+=arr.get(i);if(subArraySum<0){subArraySum=0;}subArraySumMax=Math.max(subArraySumMax,subArraySum);//this is to get the max subsequence sumIntegervalue=arr.get(i);if(value>0){sumSubSequence+=value;}}if(sumSubSequence>0){results.add(subArraySumMax);results.add(sumSubSequence);}else{//there are no positive values so we pick the highest valuefinalintmax=Collections.max(arr);results.add(max);results.add(max);}returnresults;}
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 →