hdu 6205 card card card 最大子段和

#include<iostream>

#include<deque>

#include<memory.h>

#include<stdio.h>

#include<map>

#include<string>

#include<algorithm>

#include<vector>

#include<math.h>

#include<stack>

#include<queue>

#include<set>

#define INF 1<<29

using namespace std;

const int maxn = ;

int A[maxn];

int B[maxn];

int C[maxn*+];//A,B数组的差，在尾部复制一遍，模拟循环

int D[maxn*+];//C数组的前缀和

int N;

inline void scan_d(int &ret){

    char c;

    ret = ;

    while ((c = getchar()) < '' || c > '');

    while (c >= '' && c <= '')

    {

        ret = ret *  + (c - ''), c = getchar();

    }

}

int main (){

    while(~scanf("%d", &N)){

        memset(D,,sizeof(D));

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

            scan_d(A[i]);

        for(int i=;i<=N;i++){

            scan_d(B[i]);

            C[i]=A[i]-B[i];

            C[N+i]=A[i]-B[i];

            D[i]=C[i]+D[i-];

        }

        for(int i=N+;i<=N+N;i++){

            D[i]=C[i-N]+D[i-];

        }

        for(int i=;i<=N;i++){

             for(int j=i;j<=i+N;j++){

                 if(D[j]-D[i-]<)//如果不能取了，即i~j的和变为负数了

                 {

                     i+=j-i;//把前面i堆放到后面去，然后继续判断

                     break;

                 }

                 //如果成功取完，输出i-1，即是答案

                 if(j==N){

                     printf("%d\n",i-);

                     i=N;

                 }

             }

        }

    }

    return ;

}

最大字段和 O(N)

//3d4-1 最大子段和问题的动态规划算法

#include "stdafx.h"

#include <iostream>

using namespace std;

int MaxSum(int n,int *a);

int main()

{

    int a[] = {-,,-,,-,-};

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

    {

        cout<<a[i]<<" ";

    }

    cout<<endl;

    cout<<"数组a的最大连续子段和为:"<<MaxSum(,a)<<endl;

    return ;

}

int MaxSum(int n,int *a)

{

    int sum=,b=;

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

    {

        if(b>)

        {

            b+=a[i];

        }

        else

        {

            b=a[i];

        }

        if(b>sum)

        {

            sum = b;

        }

    }

    return sum;

}