最大和相邻子数组

Question

在一个数组中找到一个相邻的子数组，长度为N的A的和最大。

输入格式：

第一个也是唯一一个参数包含一个整数数组A。

输出格式：

返回一个整数，表示连续子数组的最大可能和。

约束条件：

1 <= N <= 1e6 -1000 <= Ai <= 1000

例如：

输入1: A= 1，2，3，4，-10

输出1: 10

解释1:子数组1，2，3，4的最大可能和为10。

输入2: A= -2，1，-3，4，-1，2，1，-5，4

输出2: 6

解释2:子数组4，-1,2,1的最大可能和为6。

你能告诉我为什么下面的代码不能工作吗?代码中的错误是什么？

public class Solution {

public int maxSubArray(final List<Integer> A) {

    ArrayList<Integer> al = new ArrayList<Integer>();
    int sum = 0;
    int max = A.get(0);
    int min = A.get(0);
    for(int i = 0;i < A.size();i++){

        sum += A.get(i);
        al.add(sum);
        if(sum > max) max = sum;

    }

    //to find the min till the index of max
    for(int i = 0; al.get(i) != max;i++) {
        if(al.get(i) < min) min = al.get(i);
    }



    if(min < 0)return max-min;
    else return max;
}



}

Answer 1

假设有这样的情况

A = [-120, -202, -293, -60, -261, -67, 10]

所以在开始的时候

max = -120 
min = -120

现在，在第一个循环中，你的最大值不会改变，它将保持在-120，因为和总是小于-120。

而且你的第二个循环也不会运行，

al.get(i) = -120和max = -120，则al.get(i) != max将为false。

Answer 2

老实说，我不知道你到底想做什么，但不管怎样，在这里留下代码样本，这是使用动态编程方法解决这个问题的非常流行和简单的方法。这也称为Kadane's algorithm

public static int name(List<Integer> numbers) {

    int maxSum = numbers.get(0);
    int tempMax = maxSum;

    for (int i = 1; i < numbers.size(); i++) {
        tempMax = Math.max(numbers.get(i), numbers.get(i) + tempMax);
        maxSum = Math.max(maxSum, tempMax);
    }

    return maxSum;
}