Максимальная сумма смежных подмассивов

Question

Найти непрерывный подмассив в массиве A длиной N с наибольшей суммой.

Формат ввода:

Первый и единственный аргумент содержит целочисленный массив A.

Формат вывода:

Возвращает целое число, представляющее максимально возможную сумму непрерывного подмассива.

Ограничения:

1 <= N <= 1e6 -1000<= A [i] <= 1000 </p>

Например:

Вход 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

Честно говоря, я не получил именно то, что вы пытаетесь сделать, но в любом случае оставил здесь пример кода, который довольно популярен и прост для этой проблемы с использованием подхода динамического программирования.Это также так называемый алгоритм Кадане

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