UVa 507 - Jill Rides Again

题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=448

类型： 最大连续和

原题:

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 first part of her trip. When the bus reaches some pleasant part of the city, Jill gets off 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 finish 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 different 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 file contains information on several bus routes. The first line of the file is a single integerbrepresenting the number of route descriptions in the file. The identifier for each route (r) is the sequence number within the data file,. Each route description begins with the number of stops on the route: an integers,on a line by itself. The number of stops is followed bys- 1 lines, each linei() is an integern_irepresenting Jill's assessment of the niceness of the road between the two stopsiandi+1.

Output

For each routerin the input file, your program should identify the beginning bus stopiand the ending bus stopjthat identify the segment of the route which yields the maximal sum of niceness, m= n_i+n_i+1+...+n_j-1. If more than one segment is maximally nice, choose the one with the longest cycle ride (largestj-i). To break ties in longest maximal segments, choose the segment that begins with the earliest stop (lowesti). For each routerin the input file, print a line in the form:

The nicest part of routeris between stopsiandj

However, if the maximal sum is not positive, your program should print:

Routerhas no nice parts

Sample Input

3
3
  -1
   6
10
   4
  -5
   4
  -3
   4
   4
  -4
   4
  -5
4
  -2
  -3
  -4

Sample Output

The nicest part of route 1 is between stops 2 and 3
The nicest part of route 2 is between stops 3 and 9
Route 3 has no nice parts

题目大意：

题目说得天花乱坠， 简单说来就是一段公交车路，各个车站为1,2,3...s, 各个车站之间的这段路好感值是不同的， 例如车站1到车站2的好感度是5， 车站3到车站4的好感度是-3. 求一段连续的车站的好感度之和最大是多少。

分析与总结：

最大连续和问题，有好几种算法，其中最快的一种是O(n)的，只需要扫描一遍即可。

假设用数组arr存好感度 , 那么设sum[i]=arr[0]+arr[1]+..+arr[i]. 即sum[i]是从车站1到车站i的好感度之和。 这样的话，如果要求某一段车站的好感度之和， 假设车站3到车站5，只需要O（1）时间： sum[5]-sum[2]就是答案。

要使得sum[i]-sum[j]更大，就要使得sum[j]更小。

做题时需要注意的是，答案要求好感度最大的连续和区间长度越长越好， 起点越早越好。

代码：

/*
 * UVa: 507 - Jill Rides Again
 * Time: 0.120s
 * Author: D_Double
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 20005
using namespace std;
int b,s;
int arr[MAXN];

int main(){
    scanf("%d",&b);
    for(int t=1; t<=b; ++t){
        scanf("%d",&s);
        arr[0]=0;
        for(int i=1; i<=s-1; ++i){
            scanf("%d",&arr[i]);
            arr[i] += arr[i-1];
        }

        int min=0, maxSum=-2147483646, left=0, right=0;

        for(int i=1; i<=s-1; ++i){
            int t=arr[i]-arr[min];
            if(t>maxSum) { maxSum=t; right=i; left=min; }
            else if(t==maxSum) { // 这个特别要注意！！！因为题目要求区间越长越好
                if(min==left)
                    right=i; 
                else if(i-min > right-left)
                    right=i, left=min;
            }
            if(arr[i]<arr[min]) { min=i;}
        }

        if(maxSum>0){
            printf("The nicest part of route %d is between stops %d and %d\n", t, left+1, right+1);
        }
        else{
            printf("Route %d has no nice parts\n", t);
        }
    }
    return 0;
}

附：这个算法的升级版：UVa 108 - Maximum Sum

—— 生命的意义，在于赋予它意义。

    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)