程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Max Sum(hdu

Max Sum(hdu

編輯:關於C++

一道很有意思的dp,說它有意思是因為他的原理其實很簡單,而且掃描一次就可以得到最終的答案。

如果當前這個數之前的和小於0,那麼最大和就從當前的數重新開始;否則最大和就是之前的和加上當前這個數。

這樣為什麼是正確的呢? 我們假設當前這個數之前的連續和小於0,那麼他對下面的貢獻是負的,所以無論後面的數有多大,最大連續和肯定都不如捨棄前面負貢獻的和大。

然後每次更新dp[i]的最大值,就相當於由枚舉的連續和的終點。

 

#include
#include
#include
#include
using namespace std;
int T,n,a[100005],dp[100005];
int main(){
    scanf("%d",&T);
    int kase = 0;
    while(T--){
        scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        printf("Case %d:\n",++kase);
        int ans = -1000000000,x1,x2,l,r;
        dp[1] = a[1];
        x1 = 1; ans = dp[1];
        l=1; r=1;
        for(int i=2;i<=n;i++){
            if(dp[i-1]<0) {
                x1 = i;
                dp[i] = a[i];
            } else dp[i] = dp[i-1] + a[i];
            if(ans

 

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