Find array of maximum subarray sum using kadane's Algorithm

Question

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

Answer 1

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);
    }
}