首页 > 代码库 > 最大子序列和，最小子序列和，最小正子序列和，最大子序列乘积
最大子序列和，最小子序列和，最小正子序列和，最大子序列乘积
来自：《数据结构与算法分析——C语言描述》练习2.12
一. 最大子序列和
1.穷举法，O（N3）
1 int maxSequenceSum1(const int A[], int N) 2 { 3 int i, j, k, maxSum, thisSum; 4 5 maxSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 for (j = i; j < N; j++) 9 {10 thisSum = 0;11 for (k = i; k <= j; k++)12 thisSum += A[k];13 14 if (thisSum > maxSum)15 maxSum = thisSum;16 }17 }18 return maxSum;19 }
2.撤一个for，O（N2）
1 int maxSequenceSum2(const int A[], int N) 2 { 3 int i, j, maxSum, thisSum; 4 5 maxSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 thisSum = 0; 9 for (j = i; j < N; j++)10 {11 thisSum += A[j];12 13 if (thisSum > maxSum)14 maxSum = thisSum;15 }16 }17 return maxSum;18 }
3.分治算法，O（NlogN）
1 int maxSubSum(const int A[], int left, int right) 2 { 3 int maxLeftSum, maxRightSum; 4 int maxLeftBorderSum, maxRightBorderSum; 5 int leftBorderSum, rightBorderSum; 6 int center, i; 7 8 if (left == right) /*Base case*/ 9 {10 if (A[left] > 0)11 return A[left];12 else13 return 0;14 }15 16 center = (left + right) / 2;17 maxLeftSum = maxSubSum(A, left, center);18 maxRightSum = maxSubSum(A, center + 1, right);19 20 maxLeftBorderSum = 0; leftBorderSum = 0;21 for (i = center; i >= left; i--)22 {23 leftBorderSum += A[i];24 if (leftBorderSum > maxLeftBorderSum)25 maxLeftBorderSum = leftBorderSum;26 }27 28 maxRightBorderSum = 0; rightBorderSum = 0;29 for (i = center + 1; i <= right; i++)30 {31 rightBorderSum += A[i];32 if (rightBorderSum > maxRightBorderSum)33 maxRightBorderSum = rightBorderSum;34 }35 return max(maxLeftSum, maxRightSum,36 maxLeftBorderSum + maxRightBorderSum);37 }38 39 int maxSequenceSum3(const int A[], int N)40 {41 return maxSubSum(A, 0, N - 1);42 }
4.联机算法，O（N）
1 int maxSequenceSum4(const int A[], int N) 2 { 3 int i, maxSum, thisSum; 4 5 maxSum = 0; thisSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 thisSum += A[i]; 9 10 if (thisSum> maxSum)11 maxSum = thisSum;12 else if (thisSum < 0)13 thisSum = 0;14 }15 return maxSum;16 }
我们仍然采用更优的联机算法来求解最小子序列和、最小正子序列和、最大子序列乘积。
二.最小子序列和
1 int minSequenceSum(const int A[],int N) 2 { 3 int minSum, thisSum, i; 4 5 minSum = 0; thisSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 thisSum += A[i];; 9 10 if (thisSum < minSum)11 minSum = thisSum;12 else if (thisSum>0)13 thisSum = 0;14 }15 return minSum;16 }
三.最小正子序列和
1 int minPositiveSubSum(const int A[], int N) 2 { 3 int minSum, thisSum, i; 4 5 minSum = 0x7FFFFFFF; thisSum = 0; 6 for (i = 0; i < N; i++) 7 { 8 thisSum += A[i]; 9 10 if (thisSum < minSum && thisSum > 0)11 minSum = thisSum;12 else if (thisSum < 0)13 thisSum = 0;14 }15 return minSum;16 }
四.最大子序列乘积
1 int maxPositiveSubMul(const int A[], int N) 2 { 3 int maxMul, thisMul, i; 4 5 maxMul = 1; thisMul = 1; 6 for (i = 0; i < N; i++) 7 { 8 thisMul *= A[i]; 9 10 if (thisMul > maxMul)11 maxMul = thisMul;12 }13 14 return maxMul;15 }
最大子序列和，最小子序列和，最小正子序列和，最大子序列乘积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。