题目
Jill likes to ride her bicycle, but since the pretty city of Greenhills where she lives has grown, Jill often uses the excellent public bus system for part of her journey. She has a folding bicycle which she carries with her when she uses the bus for the ?rst part of her trip. When the bus reaches some pleasant part of the city, Jill gets o? and rides her bicycle. She follows the bus route until she reaches her destination or she comes to a part of the city she does not like. In the latter event she will board the bus to ?nish her trip.
Through years of experience, Jill has rated each road on an integer scale of “niceness.” Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. There are not zero values. Jill plans where to leave the bus and start bicycling, as well as where to stop bicycling and re-join the bus, so that the sum of niceness values of the roads she bicycles on is maximized. This means that she will sometimes cycle along a road she does not like, provided that it joins up two other parts of her journey involving roads she likes enough to compensate. It may be that no part of the route is suitable for cycling so that Jill takes the bus for its entire route. Conversely, it may be that the whole route is so nice Jill will not use the bus at all.
Since there are many di?erent bus routes, each with several stops at which Jill could leave or enter the bus, she feels that a computer program could help her identify the best part to cycle for each bus route.
Input
The input ?le contains information on several bus routes. The ?rst line of the ?le is a single integer b representing the number of route descriptions in the ?le. The identi?er for each route ? is the sequence number within the data ?le, 1 ≤ r ≤ b. Each route description begins with the number of stops on the route: an integer s, 2 ≤ s ≤ 20,000 on a line by itself. The number of stops is followed by s?1 lines, each line i (1 ≤ i < s) is an integer ni representing Jill’s assessment of the niceness of the road between the two stops i and i + 1.
Output
For each route r in the input ?le, your program should identify the beginning bus stop i and the ending bus stop j that identify the segment of the route which yields the maximal sum of niceness, m = ni + ni+1 + … + nj?1 . If more than one segment is maximally nice, choose the one with the longest cycle ride (largest j ?i). To break ties in longest maximal segments, choose the segment that begins with the earliest stop (lowest i). For each route r in the input ?le, print a line in the form:
The nicest part of route r is between stops i and j
However, if the maximal sum is not positive, your program should print:
Route r has no nice parts
思路
经典动态规划(也是贪心)问题——求一个序列中最大子序列和，这里简述一下算法：
1：初始化结果ans = 0，累加0到n-1个元素，每一步得到一个和sum；
2：如果某一步中sum > ans，更新ans；
3：如果sum < 0，重置sum为0；
最终ans中储存的即最大子序列和。相关证明需要自行查阅资料。
本体的额外要求是要记录这个和最大的最大子序列的起始点，尽可能的包含更多的元素
代码
#include <iostream>
#include <algorithm>
using namespace std;
int n[20010];
int main()
{
int TC, r, cot = 1;scanf("%d", &TC);while(TC--){
scanf("%d", &r);int ans = 0, sum = 0, r1 = 1, r2 = 0, ans_r1 = 1, ans_r2 = 0;for(int i = 1; i < r; i++) scanf("%d", &n[i]);for(int i = 1; i < r; i++){
sum += n[i]; r2 = i + 1;if(sum < 0){
r1 = i + 1; sum = 0; }else if(sum > ans || (sum == ans && r2 - r1 > ans_r2 - ans_r1)){
ans = sum; ans_r2 = r2; ans_r1 = r1; }}if(ans > 0) printf("The nicest part of route %d is between stops %d and %d\n", cot++, ans_r1, ans_r2);else printf("Route %d has no nice parts\n", cot++);}
}