浙江大學-數據結構-作業-Maximum Subsequence Sum

01-複雜度2 Maximum Subsequence Sum（25 分）

Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni+1, ..., Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10

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

Sample Output:

10 1 4

這題是上一道最大子列和問題的加強版，要找到最大子列和的起始和終止位置，這題我想了挺久的。。。先放代碼，再講思路。。。

python版

#! python3# -*- coding: utf-8 -*-def max_sub_seq_sum(k, array): this_sum = 0 max_sum = 0 for i in range(k): this_sum += array[i] if this_sum > max_sum: max_sum = this_sum elif this_sum < 0: this_sum = 0 return max_sumdef max_sub_seq_sum_improve(k, array): this_sum = 0 max_sum = 0 end = 0 flag = 0 for i in range(k): if array[i] > 0: flag = 1 this_sum += array[i] if this_sum > max_sum: max_sum = this_sum end = i # 終點有可能就是大於最大和的位置 elif this_sum < 0: this_sum = 0 # print(end) # 通過終點反推起點 if flag == 0: # 如果全是負數 start = 0 end = k - 1 max_sum = 0 else: temp_sum = 0 temp_index = end while temp_sum != max_sum: temp_sum += array[temp_index] temp_index -= 1 # if temp_index == 1: # debug, 當index移動到1的時候，結果加起來只是9，而不是10 # print(temp_sum) start = temp_index + 1 # 多減了一個，所以要加1 return max_sum, start, enddef main(): # k = 10 test_k = 10 test = [-10, 1, 2, 3, 4, -5, -23, 3, 7, -21] max_sum, start, end = max_sub_seq_sum_improve(test_k, test) print(max_sum, start, end) # array = [-10, 1, 2, 3, 4, -5, -23, 3, 7, -21]if __name__ == __main__: main()

c版

#include <stdio.h>struct Tuple { int start; int end; int max_sum;};struct Tuple max_sub_seq_sum(int k, int array[]){ int this_sum = 0, max_sum = 0; int i; int start = 0, end = 0; int flag = 0; for (i = 0; i < k; i++){ if (array[i] > 0){ flag = 1; } this_sum += array[i]; if (this_sum > max_sum){ max_sum = this_sum; end = i; /*possible exit index*/ } else if (this_sum < 0){ this_sum = 0; } } if (flag == 0){ /*all negatives*/ struct Tuple res = {0, k-1, 0}; // start, end, max_sum return res; } else{ int temp_sum = 0; int temp_index = end; while(temp_sum < max_sum){ temp_sum += array[temp_index]; temp_index -= 1; } start = temp_index + 1;// printf("%d", start); struct Tuple res = {start, end, max_sum}; return res; }}int main(){ int k = 10; int array[k] = {-10, 1, 2, 3, 4, -5, -23, 3, 7, -21}; struct Tuple res = max_sub_seq_sum(k, array); printf("%d
", res.start); printf("%d
", res.end); printf("%d
", res.max_sum); return 0;}

主要就是在之前在線處理的線性演算法上進行改進，當this_sum > max_sum時，是有可能找到最大子列的，所以這裡應該是最大子列的終點，但起點要怎麼找呢？我的思路是當知道最大子列和後，從終點推起點，將temp_sum設為0，然後從終點元素一直加到起點元素，退出條件就是temp_sum等於max_sum的時候，這個時候要注意其實是多減了一個下標的，所以我debug的時候，特意去temp_index == 1時，temp_sum的值。。。C語言版的話就是要注意不能像python一樣返回多個元素，要放到一個結構體中再返回，或者用指針。