javaarraylistkadanes-algorithm

Find array of maximum subarray sum using kadane's Algorithm


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


Solution

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