java - 连续子数组的最大和

Question

查找数组中长度为 N 且总和最大的连续子数组 A。

输入格式:

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

输出格式:

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

限制:

1 <= N <= 1e6-1000 <= A[i] <= 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 将是错误。