最大连续子序列和-动态规划

快来打我* 2022-09-23 10:51 145阅读 0赞

# 题目描述： #

给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序中元素和最大的一个， 例如给定序列\{ -2, 11, -4, 13, -5, -2 \}，其最大连续子序列为\{ 11, -4, 13 \}，最大和为20。

# 注意： #

最大连续子序列和如果为负，则返回0；而本题目中的最大连续子序列和并不返回0，如果是全为负数，则返回最大的负数即可。

# 思路分析： #

\-具有最优子结构，和重叠子问题， 动态规划的算法思路

*  最大连续子序列和只可能是以位置0～n-1中某个位置结尾。当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。
 *

## 状态转移方程： sum\[i\]=max(sum\[i-1\]+a\[i\],a\[i\]) ##

## 代码： ##

int maxsequence3(int a[], int len)  
    {  
        int maxsum, maxhere;  
        maxsum = maxhere = a[0];   //初始化最大和为a【0】  
        for (int i=1; i<len; i++) {  
            if (maxhere <= 0)  
                maxhere = a[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]  
            else  
                maxhere += a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和  
            if (maxhere > maxsum) {  
                maxsum = maxhere;  //更新最大连续子序列和  
            }  
        }  
        return maxsum;  
    }

参考：  
[http://blog.csdn.net/sgbfblog/article/details/8032464][http_blog.csdn.net_sgbfblog_article_details_8032464]  
[http://blog.csdn.net/zmazon/article/details/8247015][http_blog.csdn.net_zmazon_article_details_8247015]

[http_blog.csdn.net_sgbfblog_article_details_8032464]: http://blog.csdn.net/sgbfblog/article/details/8032464
[http_blog.csdn.net_zmazon_article_details_8247015]: http://blog.csdn.net/zmazon/article/details/8247015