Наибольшая сумма неубывающей последовательности

Question

например. -3,6,11,13,5, -11,4,7,8 наибольшая сумма = 30 (6,11,13, причина добавления -3 уменьшит сумму)

например. 7,0, -3 наибольшая сумма = 7

например 4, -1,45 наибольшая сумма = 45

например, -3 -, - 2, -6,0 наибольшая сумма = 0

Нужен совет для моего кода, все еще глючит

    int maxSum = Integer.MIN_VALUE;
    int sum = 0;
    int checkNeg = Integer.MIN_VALUE;

    for (int i = 0; i < a.length; i++) {
        if (a[i] > checkNeg) {
            checkNeg = a[i];
        }
    }

    if (checkNeg <= 0) {
        maxSum = checkNeg;
    }

    if (checkNeg > 0) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                sum += a[i];
                if (sum > maxSum) {
                    if (i != 0) {
                        if (a[i] >= a[i - 1]) {
                            maxSum = sum;
                        } else {
                            sum = a[i];
                        }
                    } else {
                        maxSum = sum;
                    }
                }
                if (sum < 0) {
                    sum = 0;
                }
            } else {
                sum = 0;
            }
        }
    }
    return maxSum;

Answer 1

Попробуйте это

        int maxSum = Int32.MinValue;
        int sum = 0;

            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] >= 0)
                {
                    sum += a[i];
                    maxSum = Math.Max(sum, maxSum);

                    if ((i+1<a.Length) && (a[i+1] < a[i]))
                        sum = 0;
                }
                else
                {
                    maxSum = Math.Max(a[i], maxSum);
                    sum = 0;
                }
            }

        return maxSum;

, похоже, подойдет для всех ваших примеров и нескольких других.

Нет необходимости в 'checkNeg', эта проверка должна исходить из алгоритма немного более естественно