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?
CodePudding user response：
You are quiet close with your approach. There are two problems with the last part:
int greatest = Integer.MAX_VALUE;should beInteger.MIN_VALUEinstead.- 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.
CodePudding user response：
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;
}
CodePudding user response：
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);
}
CodePudding user response：
It could be done in O(n) both time and space, and with more comprehensible code.
This approach requires only two iterations over the source list.
For that you need, first, calculate the greatest possible sum by using the Kadane's algorithm.
And then iterate over the source list tracking the current sum, when it's equal to maximum sum would mean the target set of consecutive elements was found.
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));
}
public static List<Integer> solution(List<Integer> nums) {
if (nums.size() == 0) {
return Collections.emptyList();
}
List<Integer> result = new ArrayList<>();
result.add(nums.get(0));
final int maxSum = getMaxSum(nums); // getting max sum by using Kadane's algorithm
int curSum = nums.get(0);
for (int i = 1; i < nums.size(); i ) {
if (curSum == maxSum) {
break; // maximus sub-array was found
}
if (nums.get(i) > curSum nums.get(i)) {
result = new ArrayList<>();
curSum = nums.get(i);
} else {
curSum = nums.get(i);
}
result.add(nums.get(i));
}
return result;
}
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;
}
output
[17, 0, 0, 9, 20, 7]
CodePudding user response：
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);
}