uva 507 - Jill Rides Again

題目意思：   有一個人想要騎自行車去旅游，但是現在有s-1條路，每一條都有一個值，正值表示他喜歡然後他會騎自行車，負數表示他不喜歡他做公交。現在問這根騎自行車的最長的道路

解題思路：
1思路：DP，最大子段和的變形
2題目輸出要求：1 如果max小於0，輸出 “Route %d has no nice parts\n"，否則輸出其它;  2如果有多個相同的max，輸出序列最長的，如果最長的也有多個輸出起始點最小的。
3解題過程分析：按照求最大的子段和的思路去求max，在更新max的時候注意要更新起始點位置和終點位置

代碼：
[cpp] 
#include <algorithm>   
#include <iostream>  
#include <cstring> 
#include <cstdio>  
using namespace std; 
#define MAXN 20010 
 
int t , s; 
int value[MAXN]; 
long long  dp[MAXN]; 
int start , end , len; 
 
void solve(int k){ 
    long long max; 
    int tmpStart , tmpEnd , tmpLen; 
    memset(dp , 0 , sizeof(dp)); 
    start = 1 ; end = 2 ; len = 1; 
    tmpStart = 1 ; tmpEnd = 2 ; tmpLen = 1; 
    dp[1] = value[1] ; max = dp[1]; 
    for(int i = 2 ; i < s; i++){/*枚舉每一個點*/ 
        if(dp[i-1] >= 0){/*如果dp[i-1]>=0*/ 
            dp[i] = dp[i-1]+value[i]; 
            tmpEnd = i+1 ;  tmpLen++ ;/*更新tmpEnd 和tmpLen*/ 
            if(max < dp[i]){/*如果max小於dp[i]，更新max和start 和end 和len*/ 
                max = dp[i] ;  
                start = tmpStart ; end = tmpEnd; 
                len = tmpLen; 
            } 
            else if(max == dp[i]){/*相等的時候也要判斷當前的長度tmpLen 是否大於len*/ 
                if(tmpLen > len){ 
                   start = tmpStart ; end = tmpEnd; 
                   len = tmpLen; 
                } 
            } 
        } 
        else { /*如果dp[i-1] < 0 */ 
            dp[i] = value[i] ; tmpStart = i; 
            tmpEnd = i+1 ; tmpLen = 1;/*更新tmpEnd 和tmpLen*/ 
            if(max < dp[i]){/*如果max < dp[i],更新max 和 start和end 和len*/ 
                max = dp[i] ; len = tmpLen; 
                start = tmpStart ; end = tmpEnd; 
            } 
        } 
    } 
    printf("The nicest part of route %d is between stops %d and %d\n",k , start , end); 
} 
 
int main() { 
    //freopen("input.txt" , "r" , stdin); 
    int i , k , flag; 
    scanf("%d%*c" , &t); 
    for(k = 1 ; k <= t ; k++){ 
        scanf("%d*c" , &s) ; flag = 0;/*flag 標記是否出現正數*/ 
        for(i = 1 ; i < s; i++){ 
            scanf("%d*c" , &value[i]); 
            if(value[i] > 0) flag = 1; 
        } 
        if(flag) solve(k); 
        else printf("Route %d has no nice parts\n" , k); 
    } 
    return 0; 
}