一道简单的题目,大家来看看,看谁写的简单速度快.

Question

Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
 Sample Output
Case 1:
14 1 4Case 2:
7 1 6描述一下,给你一个序列的数,找出和为最大的子序列,
例如第一个, 5表示有5个数, 6 -1 5 4 -7的时候
和为14 下标是1到 4
所以输出为14 1 4
期待高手~~~

Answer 1

#include <iostream>
using namespace std;#define MAX_N 10struct info{
int from, sum;
};int main(){
int c, n, a;
info rec[MAX_N];
cin >> c;
for (int ci = 0; ci < c; ++ci){
int maxi = -1;
cin >> n;
for (int i = 0; i < n; ++i){
cin >> a;
if (i == 0 || rec[i-1].sum < 0){
rec[i].from = i;
rec[i].sum = a;
if (i == 0) maxi = i;
} else {
rec[i].from = rec[i-1].from;
rec[i].sum = rec[i-1].sum + a;
}
if (rec[i].sum > rec[maxi].sum) maxi = i;
}
cout << rec[maxi].sum << " " << rec[maxi].from + 1 << " " << maxi + 1 << endl;
}
return 0;
}