最大子序列和——HDU-1003 Max Sum

题目大意：给定序列个数n及n个数，求该序列的最大连续子序列的和，要求输出最大连续子序列的和以及子序列的首位位置

解题思路：经典DP，可以定义dp[i]表示以a[i]为结尾的子序列的和的最大值，因而最大连续子序列及为dp数组中的最大值。

　　　　　　状态转移方程：dp[1] = a[1]; //以a[1]为结尾的子序列只有a[1]；

　　　　　　　　　　　　　　 i >= 2时， dp[i] = max( dp[i-1]+a[i], a[i] );

　　　　　　　　dp[i-1]+a[i] > a[i]时，即dp[i-1](以a[i-1]为结尾的子序列的和的最大值)的值为正，那么dp[i-1]则对dp[i]有贡献，

　　　　　　　　dp[i-1]+a[i] < a[i]时，即dp[i-1] < 0，那么抛弃它，dp[i] = a[i]

例子：序列 6 -7 5 2 -3，则dp[i]分别为 6 -1 5 7 4，注意dp[2]直接用a[2]表示，因为dp[1] = -1 < 0; 最后最大子序列和即为dp数组中的最大值 5;

至于位置的记录，则再每次获取到最大值时更新即可。另外此题是从前往后更新，可直接使用a[i]数组而省下一个dp数组。

//最大子序列和

#include <iostream>

#include <cstdio>

#include <math.h>

#include <string.h>

#include <string>

using namespace std;

int dp[];

int t,m,l,r,start,maxx;

int main()

{

    scanf("%d",&t);

    for(int i=;i<=t;i++)

    {

        scanf("%d",&m);

        for(int j=;j<=m;j++)

        {

            scanf("%d",&dp[j]);

        }

        l = r = start = ;

        maxx = dp[];

        for(int j=;j<=m;j++)

        {

            if(dp[j-] >= )

                dp[j] = dp[j-] +dp[j];

            else

                start = j;

            if(dp[j] > maxx){

                maxx = dp[j];

                l = start;

                r = j;

            }

        }

        cout <<"Case "<<i<<":\n"<<maxx<<" "<<l<<" "<<r<<endl;

        if(i != t)

            cout<<endl;

    }

    return ;

}

第二种解法，直接在输入的时候判断是否形成最大子序列，如果数列小于零，则一直重排，不过maxx最好定义的足够小，否则会因为全部是负数这个点wa掉

#include <iostream>

#include <math.h>

#include <cstdio>

using namespace std;

int main()

{

    int t;

    scanf("%d",&t);

    for(int i=;i<=t;i++)

    {

        int m,k;

        int maxx = -,sum = ,l = ,r = ,cnt = ,temp;// l 不是左下标 而是maxx序列的个数

        scanf("%d",&m);

        int m2 = m;

        while(m--)

        {

            scanf("%d",&k);

            sum += k;

            cnt++;

            if(sum > maxx){

                l = cnt;

                maxx = sum;

                r = m2 - m;

            }

            if(sum < ){

                sum = ;

                cnt = ;

            }

        }

        cout <<"Case "<<i<<":\n"<<maxx<<" "<<r-l+<<" "<<r<<endl;

        if(i != t)

            cout<<endl;

    }

    return ;

}

巴特西

最大子序列和——HDU-1003 Max Sum

最新文章

热门文章