Find the maximum sum of contiguous non-empty subarray and its elements within an array Arr of length N.
import java.util.*;
public class MaximumSubarraySum {
public static void main(String[] args) {
ArrayList<Integer> Arr = new ArrayList<Integer>(Arrays.asList(-2,-3,4,-1,-2,1,5,-3));
int currSum = 0,maxSum = Integer.MIN_VALUE;
for(int i = 0 ; i < Arr.size(); i++) {
currSum = currSum + Arr.get(i);
maxSum = Math.max(maxSum, currSum);
if(currSum < 0) currSum = 0;//reset currSum when its negative value
}
System.out.print(maxSum);
}
}
I could get the maxSum among the subarray sums but, how can i store the subarray elements which is contributing to maxSum while traversing the array using this algorithm? Expected output : 4,-1,-2,1,5
You can keep track of the start and end indexes of the maximum sum array. After traversing, you can create a subarray from the main array and use it where needed.
import java.util.ArrayList;
import java.util.Arrays;
public class MaximumSubarraySum {
public static void main(String[] args) {
ArrayList<Integer> Arr = new ArrayList<Integer>(Arrays.asList(-2, -3, 4, -1, -2, 1, 5, -3));
int currSum = 0, maxSum = Integer.MIN_VALUE;
int start = 0, end = 0;
for (int i = 0; i < Arr.size(); i++) {
currSum = currSum + Arr.get(i);
if (currSum > maxSum) {
maxSum = currSum;
end = i;
}
if (currSum < 0) {
currSum = 0;
start = i + 1;
}
}
ArrayList<Integer> subarray = new ArrayList<>(Arr.subList(start, end + 1));
System.out.println("Max sum sub array: " + subarray);
final int maxSumValue = subarray.stream().mapToInt(Integer::intValue).sum();
System.out.println("Max Sum: " + maxSumValue);
}
}