HDU

最近刷题突然发现vj上还有几道很久以前的attempt题没有解决，所以就当水题把这些题补了....

原题链接

题意：

求给出序列的最大连续子序列，同时输出其区间 (如果有相同的最大值区间，输出 i , j 最小的区间)

思路：

求最大连续子序列：递推公式 dp[i] = max ( arr[i] , dp[i-1] + arr[i] ) , 表示以 i 结尾的最大连续子序列和。 最后遍历一遍 输出最大 dp 值即可.

关于区间范围我们 就写个结构体记录一下即可，在递推时候进行更新。

code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 10005
const int inf = 0x3f3f3f3f;
struct node{
    int l,r;
    int val;
}dp[maxn];
int arr[maxn];
int main()
{
    int n,mmax,flag;
    while(cin>>n&&n)
    {
        mmax=-inf , flag=0;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
            if(arr[i]>=0)flag=1;
        }
         //若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素 
        if(!flag){
            cout<<0<<" "<<arr[1]<<" "<<arr[n]<<endl;
            continue;
        }
        //最大连续序列和dp
        dp[0].l = 1;
        for(int i=1;i<=n;i++){
            if(arr[i]>dp[i-1].val+arr[i]){
                dp[i].val = arr[i];
                dp[i].l = i;
                dp[i].r = i;
            }else{
                dp[i].val = dp[i-1].val + arr[i];
                dp[i].l = dp[i-1].l;
                dp[i].r = i;
            }
            mmax=max(dp[i].val,mmax);
        }
        int l,r;
        for(int i=1;i<=n;i++){
            if(dp[i].val==mmax){
                cout<<mmax<<" "<<arr[dp[i].l]<<" "<<arr[dp[i].r]<<endl;
                break;
            }
        }    
    }
    return 0;
}