01-复杂度2 Maximum Subsequence Sum (25分)

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

题目有一个测试点是“最大和前面有一段是0”，所以呢基本上就是在老师的代码的基础上做一点点的修改。每次开始新的子序列记录一个位置，当更新最大子序列和的时候更新最大子序列和的start 和 end。

#include <stdio.h>

int main(int argc, char const *argv[])
{
    int i, k;
    scanf("%d", &k);
    int numbers[k];

    for (i = 0; i < k; i++) {
        scanf("%d", &numbers[i]);
    }
    
    int best_sum, current_sum;

    int best_start, best_end, current_start;
    best_sum = -1;
    current_sum = 0;
    for (i = 0; i < k; i++) {
        current_sum += numbers[i];
        if (current_sum > best_sum) {
            best_sum = current_sum;
            best_start = current_start;
            best_end = i;
        } else if (current_sum < 0) {
            current_sum = 0;
            current_start = i + 1;
        }
    }
    if (best_sum > 0) {
        printf("%d ", best_sum);
        printf("%d %d
", numbers[best_start], numbers[best_end]);
    } else {
        printf("0 %d %d
", numbers[0], numbers[k-1]);
    }
    return 0;
}

Python 版

k = input()
numbers = list(map(int, input().split()))

best_sum = -1
current_sum = 0
best_start = best_end = current_start = 0
for current_end, x in enumerate(numbers):
    current_sum += x
    if current_sum > best_sum:
        best_sum = current_sum
        best_start = current_start
        best_end = current_end
    elif current_sum < 0:
        current_sum = 0
        current_start = current_end + 1

if best_sum >= 0:
    print(best_sum, numbers[best_start], numbers[best_end])
else:
    print(0, numbers[0], numbers[-1])