最大和邻接子阵

Question

在长度为N的数组中求和最大的邻接子数组。

输入格式：

输出格式：

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

制约因素：

输入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

老实说，我不知道您到底想做什么，但无论如何，这里的代码示例是非常流行和简单的，使用动态编程方法解决这个问题。这也被称为卡丹算法

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