程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1231最大連續子序列 動態規劃

hdu 1231最大連續子序列 動態規劃

編輯:C++入門知識

hdu 1231最大連續子序列 動態規劃


動態轉移方程dp[i]=max(dp[i-1]+a[i],a[i]);

dp[i]表示一這個點結尾的最大連續子序列

因為還要記錄序列的頭和尾,用start[]記錄每個點在該序列的起始位置

注意提示要用scanf啊,cin會TLE

/*************************************************************************
	> File Name: hdu1231.cpp
	> Author: yang
	> Mail:[email protected] 
	> Created Time: 2014年08月24日 星期日 20:01:52
 ************************************************************************/

#include
#include
#include
using namespace std;
#define N 10005
int main(){
	int n;
	int a[N],dp[N],start[N];
	while(scanf("%d",&n),n){
		int flag=0,cou=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			dp[i]=0;
			if(a[i]<0)
			cou++;
		}
		if(cou==n)
			flag=1;
		int x=1;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			if(dp[i-1]+a[i]>=a[i])
				dp[i]=dp[i-1]+a[i];
			else{
				x=i;
				dp[i]=a[i];
			}
			start[i]=x;
		}
		if(flag==0){
			cou=0;
			for(int i=1;i<=n;i++)
				if(dp[i]>cou)
					cou=dp[i];
			for(int i=1;i<=n;i++){
				if(cou==dp[i]){
					cout<

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