首页 > 其他 > 详细

dp-最大连续子序列的和

时间:2017-08-17 23:13:11      阅读:262      评论:0      收藏:0      [点我收藏+]

 

什么是最大连续子序列和呢 ?

  最大连续子序列和是所有子序列中元素和最大的一个 。

 

问题 :

  给定一个序列 { -2, 11, -4, 13, -5, -2 } , 则最大连续子序列和为 20 , 即 { 11 , -4 , 13 } 。

 

分析 :

  要怎样去解决这个问题呢 ? 设出 两个变量 , 一个 ans 用来存放最终的结果 , 一个用来现在对元素进行加和 , 每当有最大的和则更形下 ans 。

 

代码示例 :

  

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std ;

#define Min(a,b) a>b?b:a
#define Max(a,b) a>b?a:b

int main ( ) {
    int a[6] = {-2, 11, -4, 13, -5, -2 } ;

    int ans = 0 , now = 0 ;

    for ( int i = 0 ; i < 6 ; i++ ) {
        now += a[i] ;
        if ( now < 0 ) now = 0 ;
        if ( ans < now ) ans = now ;  // 每次更新 ans 的值 , 那么 ans 中存的一定是最大的元素和  
    }

    cout << ans << endl ;

    return 0 ;
}

 

题目 : HDU 1003   http://acm.hdu.edu.cn/showproblem.php?pid=1003

dp-最大连续子序列的和

原文:http://www.cnblogs.com/ccut-ry/p/7384888.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!