Finding the subarray with the Maximum sum in the given ArrayList

Question

The problem description:

Given an ArrayList of Integers. Find a subarray with the maximum sum of any potential subarray within the ArrayList.

A subarray a is a combination of consecutive numbers.

The subarray can be of any length n, where the size of n >= 0.

Example

Input:

[-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18]

Solution

[17, 0, 0, 9, 20, 0, 7]

Here is the code that I have so far.

public class MaxSubArray {

    public ArrayList<Integer> solution(ArrayList<Integer> nums) {
        int maxSubArrSum = Integer.MIN_VALUE;
        int greatest = Integer.MAX_VALUE;
        int smallest = 0;
        int start;
        int end;
        ArrayList<Integer> maxSubArr;
        ArrayList<ArrayList<Integer>> lists = new ArrayList();

        try {
            for (int left = 0; left < nums.size(); left++) {
                int runningSum = 0;
                for (int right = left; right < nums.size(); right++) {
                    runningSum += nums.get(right);
                    if (runningSum >= maxSubArrSum) {
                        ArrayList<Integer> temp = new ArrayList<>();
                        maxSubArrSum = runningSum;
                        start = left;
                        end = right;
                        for (int i = start; i <= end; i++) {
                            temp.add(nums.get(i));
                        }
                        lists.add(temp);
                    }
                }
            }

            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i).size() < greatest) {
                    greatest = lists.get(i).size();
                    smallest = i;
                }
            }
            maxSubArr = lists.get(smallest);
            return maxSubArr;
        } catch (Exception e) {
            e.printStackTrace();
            return nums;
        }
    }
}

I am trying to iterate through the nums ArrayList and figuring out the first and last indexes of the subarrays with the maximum sum and putting them in a list of ArrayLists.

After that, I am trying to figure out which of the subarrays has the smallest size and returning it.

What I am doing wrong here?

Answer 1

Here is a more concise solution

private List<Integer> solution(List<Integer> nums) {
    int biggestSumSoFar = Integer.MIN_VALUE;
    List<Integer> biggestSubListSoFar = new ArrayList<>();
    for (int left = 0; left < nums.size(); ++left) {
        for (int right = left + 1; right < nums.size(); ++right) {
            List<Integer> currentSubList = subListSum(nums, left, right);
            int currentSum = sum(currentSubList);
            if (currentSum > biggestSumSoFar) {
                biggestSumSoFar = currentSum;
                biggestSubListSoFar = currentSubList;
            }
        }
    }
    return biggestSubListSoFar;
}

private List<Integer> subListSum(final List<Integer> nums, final int left, final int right)
{
    final List<Integer> sublist = new ArrayList<>();
    for (int i = left; i < right; i++)
    {
        sublist.add(nums.get(i));
    }
    return sublist;
}

private int sum(List<Integer> arr) {
    int sum = 0;
    for(int a : arr){
        sum += a;
    }
    return sum;
}

Answer 2

Adding a third inner for-loop can make the task probably easier. Just think about how you would do it with a pen and paper. Imagine you have an array of 6 elements with indices from 0 to 5, then all possible subarrays would have the following start and end indices (strat inclusive, end exclusive)

0 - 1     1 - 2     2 - 3     3 - 4     4 - 5
0 - 2     1 - 3     2 - 4     3 - 5   
0 - 3     1 - 4     2 - 5   
0 - 4     1 - 5   
0 - 5 

Having the above all you need is to calculate the subsum and store the relevant start and end indices

public List<Integer> solution(List<Integer> nums) {
    int maxSubArrSum = Integer.MIN_VALUE;
    int start = 0;
    int end   = 0;
    for (int left = 0; left < nums.size(); left++){
        for (int right = left+1; right < nums.size(); right++){
            int subSum = 0;
            for (int k = left; k < right; k++){
                subSum += nums.get(k);
            }
            if (subSum > maxSubArrSum){
                maxSubArrSum = subSum;                    
                start = left;
                end   = right;
            }
        }
    }
    return nums.subList(start,end);
}

Answer 3

Here is a modified version of Kadane's Algorithm to find the largest sum of contiguous elements in a list. It is adapted from a solution given in Python and works in a single pass.

List<Integer> list = List.of(-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18);
List<Integer> subList = maxSubArray(list); 
System.out.println(subList);

prints

[17, 0, 0, 9, 20, 7]

public static List<Integer> maxSubArray(List<Integer> list) {
    int max = Integer.MIN_VALUE;
    int sum = max;
    int end = 0;
    int cstart = 0, start = 0;
    for (int i = 0; i < list.size(); i++) {
        int val = list.get(i);
        if (sum <= 0) {
            sum = val;
            cstart = i;
        } else {
            sum += val;
        }
        if (sum > max) {
              max = sum;
              start = cstart;
              end = i;              
        }
    }
    return list.subList(start,end+1); 
}

Answer 4

You are quiet close with your approach. There are two problems with the last part:

1. int greatest = Integer.MAX_VALUE; should be Integer.MIN_VALUE instead.
2. You check for the size of a subarray but you have to check for the sum of the subarray.

if you change the last part to:

int greatest = Integer.MIN_VALUE;
for (int i = 0; i < lists.size(); i++) {
    if (sum(lists.get(i)) > greatest) {
        greatest = lists.get(i).size();
        smallest = i;
    }
}

by utilizing

public static int sum(List<Integer> arr) {
    int sum = 0;
    for(int a : arr){
        sum += a;
    }
    return sum;
}

it yields the desired result.

Answer 5

Basically, you are trying to approach this task with a brute-force algorithm, which in the worse case scenario will have the O(n^2) both time and space complexity.

It could be done with a linear (i.e. O(n)) both time and space complexity, without nested loops.

With this approach, first, we need to find the maximum possible sum of the subarray by using the Kadane's algorithm.

And then perform the iteration with over the source list in a single loop tracking the current sum. When it becomes equal to the maximum sum it would mean the target subarray of consecutive elements was found.

Variables start and end denote the starting and ending indices of the resulting subarray.

Method subList() creates a view over the source list and every modification of the view will be reflected in the source and vice versa. Hence, as a precaution it's being wrapped with with a new instance of ArrayList.

public static List<Integer> solution(List<Integer> nums) {
    if (nums.size() == 0) {
        return Collections.emptyList();
    }

    final int maxSum = getMaxSum(nums); // getting max sum by using Kadane's algorithm
    int curSum = nums.get(0);

    int start = 0; // beginning of the resulting subarray
    int end = 0; // end of the resulting subarray exclusive

    for (int i = 1; i < nums.size(); i++) {
        if (curSum == maxSum) {
            end = i;
            break; // maximus sub-array was found
        }

        if (nums.get(i) > curSum + nums.get(i)) {
            start = i;             // setting start to current index
            curSum = nums.get(i);  // assigning the current element the sum
        } else {
            curSum += nums.get(i); // adding the current element to the sum
        }
    }
    return new ArrayList<>(nums.subList(start, end));
}

Kadane's algorithm implementation.

The overall idea is to maintain two variables denoting the global and a local maximum. There are to ways in which the local maximum changes with each iteration, we either

• adding the current element to the local maximum;
• or assigning the current element's value to the local maximum.

At the end of every iteration, the global maximum is being compared with a local maximum and adjusted if needed.

public static int getMaxSum(List<Integer> nums) {
    int maxSum = Integer.MIN_VALUE;
    int curSum = nums.get(0);
    for (int i = 1; i < nums.size(); i++) {
        curSum = Math.max(nums.get(i), curSum + nums.get(i));
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

main()

public static void main(String[] args) {
    List<Integer> source = List.of(-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18);
    System.out.println(solution(source));
}

output

[17, 0, 0, 9, 20, 7]