6-05 1,833 views
思路：
采用动态规划进行求解，令：
maxSum[k]表示子串list{0,k}的最大连续子串和,
maxSumIncludeK[k]表示子串list{0,k}中末尾为k的最大连续子串和，
则
maxSumIncludeK[k] = max(list[k],list[k]+maxSumIncludeK[k-1]),
maxSum[k] = max(maxSumIncludeK[k],maxSum[k-1])。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <stdlib.h> #include <stdio.h> int MaxSubList(int list[],int length) { int i; //maxSum[k]表示子串list{0,k}的最大连续子串和 //maxSumIncludeK[k]表示子串list{0,k}中末尾为k的最大连续子串和 int* maxSum = (int*)malloc(sizeof(int)*length); int* maxSumIncludeK = (int*)malloc(sizeof(int)*length); for (i=0;i<length;i++) { maxSum[i] = 0; maxSumIncludeK[i] = 0; } if (list[0]>0) maxSum[0] = list[0]; maxSumIncludeK[0] = list[0]; for (i=1;i<length;i++) { maxSumIncludeK[i] = list[i]; if (maxSumIncludeK[i-1]>0) maxSumIncludeK[i]+=maxSumIncludeK[i-1]; if (maxSumIncludeK[i]>maxSum[i-1]) maxSum[i] = maxSumIncludeK[i]; else maxSum[i] = maxSum[i-1]; } return maxSum[length-1]; } int main() { int list[20] = {4,9,-4,3,2,-1,-6,7,2,-3,1,5,3,-2,7,-3,9,2,-4,2}; printf("max sum:%d \n",MaxSubList(list,20)); return 0; } |
版权属于: 我爱我家
转载时必须以链接形式注明原始出处及本声明。