[PAT解题报告] Maximum Subsequence Sum
最大子数组和问题，给定一个数组，求一个子数组和最大。要输出子数组的起点和终点对应的数，输出起点终点对应下标字典序最小的，如果全是负数输出0，并且起点是第一个数，终点是最后一个数。
分析：还是那个经典算法：
以第i项结尾的最大子数组有两种可能：
（1） 以(i - 1)项结尾的最大子数组加上a[i]
（2） a[i]本身
我们要同时更新当前解的开头和结尾，注意第（2）种情况，当前解的开头变化了，变成a[i]了。我们用endi表示当前解的开头，用end表示当前解的和。我们来看看如何更新：
（1） 对应end >= 0注意等于0的时候，我们还是应该用之前的解加a[i],因为之前的解的开头更小
（2） 对应end < 0 这时我们当前解变为a[i]一个数，即endi = i ——新的开头 ,end = a[i]
如何更新最优解？ 如果当前和end > best显然要更新， 如果end == best,
要看我这个解的开头是不是更小，也就是endi < besti。
更新方式：
besti = endi;
bestj = i; //因为当前解是以i结尾的。
初值可以把best和nd设置为第一个数a[0]，besti, bestj等于0，表示就这一个数,然后再从1开始循环
特殊情况，如果best < 0，输出0，并且besti = 0, bestj = n - 1。
注意输出的是原始的数，而不是下标，所以还是要保存原来的数——当然可以用变量记录下来起点和终点以及对应的数，但那样代码不好看，索性多用一个数组了。
原始：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int a[10004];
int main() {
int n, besti = 0, bestj = 0, best, end, endi = 0;
scanf("%d%d",&n,a);
end = best = a[0];
for (int i = 1; i < n; ++i) {
scanf("%d",a + i);
if (end < 0) {
end = 0;
endi = i;
}
end += a[i];
if ((end > best) || ((end == best) && (endi < besti))) {
best = end;
besti = endi;
bestj = i;
}
}
if (best < 0) {
best = 0;
besti = 0;
bestj = n - 1;
}
printf("%d %d %d\n",best,a[besti],a[bestj]);
return 0;
}
原题链接 ： http://www.patest.cn/contests/pat-a-practise/1007
查看12道真题和解析
