程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NEUOJ 1302: 最大子序列(雙向dp)

NEUOJ 1302: 最大子序列(雙向dp)

編輯:C++入門知識

第一次寫dp,有點小激動哈哈,紀念下



1302: 最大子序列

時間限制: 1 Sec 內存限制: 128 MB
提交: 174 解決: 41
[提交][狀態][討論版]

題目描述

給定一個N個整數組成的序列,整數有正有負,找出兩段不重疊的連續子序列,使得它們中整數的和最大。兩段子序列都可以為空。

輸入

多組輸入,每組第一行為N,表示序列的長度;第二行為N個整數(-1000<=n<=1000),表示輸入序列。 0

輸出

對於每組輸入,輸出一行,僅一個整數,表示最大的和。

樣例輸入

9
185 -580 -889 701 964 -878 353 -761 608

樣例輸出

2273

提示

樣例輸入序列的一種選擇為:(701 964)和(608)


來源

#include 
#include 
#include 
using namespace std;
#define Max 1000002
int num[Max];
int dp1[Max],dp2[Max];
int main()
{
    int n;
    freopen("input.txt","r",stdin);
    while( scanf("%d",&n)!=EOF)
    {
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",num+i);
            int &temp=num[i];
            dp1[i]=dp1[i-1];
            if(sum<0)sum=temp;
            else sum+=temp;
            if(dp1[i]=1;i--)
        {
            int temp1=num[i];
            dp2[i]=dp2[i+1];
            if(sum<0)sum=temp1;
            else sum+=temp1;
            if(dp2[i]						

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved