1007. Maximum Subsequence Sum (25)

最大连续子序列和
[cpp]  
#include<iostream>  
#include<vector>  
  
int k;  
typedef struct Node  
{  
    int num;  
    int start;  
    int sum;  
}Node;  
std::vector<Node> d;  
  
int main()  
{  
    while(scanf("%d",&k)!=EOF)  
    {  
        d.resize(k);  
        for(int i = 0; i < k; ++i)  
        {  
            scanf("%d",&d[i].num);  
        }  
        //get the maximum sum  
        d[0].sum = d[0].num;  
        d[0].start = 0;  
        for(int i = 1; i < k; ++i)  
        {  
            if(d[i-1].sum >= 0)  
            {  
                d[i].sum = d[i].num+d[i-1].sum;  
                d[i].start = d[i-1].start;  
            }  
            else   
            {  
                d[i].sum = d[i].num;  
                d[i].start = i;  
            }  
        }  
        //output  
        int mmax = d[0].sum;  
        int index = 0;  
        for(int i = 1; i < k; ++i)  
        {  
            if(mmax < d[i].sum)   
            {  
                index = i;  
                mmax = d[i].sum;  
            }  
        }  
        if(mmax < 0) printf("0 %d %d\n", d[0].num, d[k-1].num);  
        else printf("%d %d %d\n", d[index].sum, d[d[index].start].num, d[index].num);  
  
    }  
    return 0;  
}  
 

补充：软件开发 , C++ ,

上一个：1004. Counting Leaves (30)
下一个：CodeSmith 生成代码解读 V1 (20130311)