Finding the subarray with the maximum sum of any potential subarray within ArrayList

0
votes

This is the problem:

Given an ArrayList of Integers, find a subarray with the maximum sum of any potential subarray within the ArrayList. A subarray is any combination of consecutive numbers. The subarray can be of any length n, where the size of n >= 0.

Example: Input Given = [-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18] Solution = [17, 0, 0, 9, 20, 0, 7]

I have been at this for hours and I am exhausted! Here is the code that I have so far

import java.util.ArrayList;

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 is the subarray with the smallest size and returning it. Does anyone see what I am doing wrong here?

javaarraylistsub-array