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

Question

问题描述：

给定一个 Integers 的 ArrayList。查找具有 ArrayList 中任何潜在子数组的最大总和的子数组。

子数组 a 是连续数字的组合。

子数组可以是任意长度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

这是 Kadane 算法的修改版本，用于查找列表中连续元素的最大总和。它改编自 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); 
}

Answer 2

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

1. int Great = Integer.MAX_VALUE; 应该改为 Integer.MIN_VALUE。
2. 您检查子数组的大小，但必须检查子数组的总和。

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

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 3

基本上，您尝试使用暴力算法来完成此任务，在最坏的情况下，该算法的时间和空间复杂度将是O(n^2) 。

它可以通过时间和空间复杂度线性（即O(n)）来完成，而无需嵌套循环。

使用这种方法，首先，我们需要使用 最大可能和 rel="nofollow noreferrer">Kadane 算法。

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

变量 start 和 end 表示结果子数组的起始和结束索引。

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

总体思路是维护两个变量，分别表示全局和局部最大值。每次迭代时局部最大值都会发生变化，我们要么将

• 当前元素添加到局部最大值中，要么将当前元素添加到局部最大值中。
• 或将当前元素的值分配给局部最大值。

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

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 4

这是一个更简洁的解决方案

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 5

添加第三个内部 for 循环可以使任务变得更容易。想想你会如何用笔和纸来做这件事。假设您有一个包含 6 个元素的数组，其索引从 0 到 5，那么所有可能的子数组都将具有以下开始和结束索引（包含 strat，不包含 end

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