最大子序列和问题
<div id="cnblogs_post_body">问题：给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大。
例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为19。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。
<div class="cnblogs_code">int max_sub_sum1(int a[],int size){ int maxSum = 0; for(int i = 0; i < size; i++ ) for(int j = 1; j < size; j++ ) { int thisSum = 0; for(int k = i; k <= j; k++ ) thisSum += a; if(thisSum > maxSum ) maxSum = thisSum; } return maxSum;}
页:
[1]