在给定的 ArrayList 中查找具有最大总和的子数组

Question

问题描述：

给出 ArrayList 的 Integers。找到 子数组 ，其中 最大总和 ArrayList 中任何潜在子数组的总和。 =21=]

一个子数组一个是连续数的组合

子数组可以是任意长度n，其中大小n >= 0.

例子

输入：

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

解决方案

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

这是我目前的代码。

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

我正在尝试遍历 nums ArrayList 并找出 first 和 last 索引具有 最大和 的 子数组 并将它们放入 ArrayList 的列表中。

之后，我试图找出 子数组 中哪个具有 最小大小 并返回它。

我做错了什么？

Answer 1

你的方法很安静。最后一部分有两个问题：

int greatest = Integer.MAX_VALUE; 应该是 Integer.MIN_VALUE。
您检查子数组的大小，但必须检查子数组的总和。

如果将最后一部分更改为：

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

利用

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

它产生了预期的结果。

Answer 2

这里有一个更简洁的解决方案

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 3

添加第三个内部 for-loop 可能会使任务更容易。想想你会如何用笔和纸来做。假设您有一个包含 6 个元素的数组，索引从 0 到 5，那么所有可能的子数组将具有以下开始和结束索引（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

有了以上所有你需要的是计算总和并存储相关的开始和结束索引

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 4

基本上，您正在尝试使用 brute-force 算法来完成此任务，在最坏的情况下，该算法将具有 O(n ^2) 时间和 space 复杂度。

它可以用线性（即O(n)）时间和space复杂度来完成，没有嵌套循环.

使用这种方法，首先，我们需要使用 Kadane's algorithm.

找到子数组的 最大可能和

然后在单个循环中对源列表执行迭代，跟踪当前总和。当它等于最大和时，表示找到了连续元素的目标子数组。

变量start和end表示结果的开始和结束索引]子数组.

方法 subList() 在源列表上创建了一个 view 并且 view 的每个修改都将反映在源中反之亦然。因此，作为预防措施，它被 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 的 算法实现.

总体思路是维护两个变量，分别表示 global 和 local 最大值。 局部最大值有多种方式随着每次迭代而变化，我们要么

将当前元素添加到局部最大值;
或将当前元素的值赋给局部最大值。

在每次迭代结束时，全局最大值与局部最大值进行比较，并在需要时进行调整。

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

输出

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

Answer 5

这里是 Kadane's Algorithm 的修改版本，用于查找列表中连续元素的最大总和。它改编自 Python 中给出的解决方案，并在一次通过中工作。

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

打印

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

在给定的 ArrayList 中查找具有最大总和的子数组

Finding the subarray with the Maximum sum in the given ArrayList

java

algorithm

arraylist

dynamic-programming

sub-array