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\n", numbers[best_start], numbers[best_end]);

    } else {

        printf("0 %d %d\n", 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])

01-复杂度2 Maximum Subsequence Sum (25分)的相关教程结束。