求非连续子序列的问题用DP很好解决,但是**分治法**就比较难了
假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S
分治法求最大非连续子序列
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答
- devmiao 2018-04-24 14:38关注
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX_N 20 int max3(int, int, int); int maxSubArrayAns(int []); int maxSubArray(int [], int, int); int main(){ int nums[MAX_N]; int i; srand(time(0)); printf("array: \n"); for(int i = 0; i < MAX_N; i++){ nums[i] = (int)(rand() % (MAX_N * 2) - MAX_N); printf("%d\t", nums[i]); } printf("\n"); printf("The max subsequen sum is %d.\n", maxSubArrayAns(nums)); return 0; } int max3(int a, int b, int c){ if(a > b) return a > c ? a : c; else return b > c ? b : c; } int maxSubArray(int nums[], int left, int right){ int maxLeftSum, maxRightSum; int maxLeftBorderSum, maxRightBorderSum; int leftBorderSum, rightBorderSum; if(left == right) if(nums[left] > 0) return nums[left]; else return 0; int mid = (left + right) / 2, i; maxLeftSum = maxSubArray(nums, left, mid); maxRightSum = maxSubArray(nums, mid + 1, right); maxLeftBorderSum = 0, leftBorderSum = 0; for(i = mid; i >= left; i--){ leftBorderSum += nums[i]; if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } maxRightBorderSum = 0, rightBorderSum = 0; for(i = mid + 1; i <= right; i++){ rightBorderSum += nums[i]; if(rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); } int maxSubArrayAns(int nums[]){ return maxSubArray(nums, 0, MAX_N - 1); }
使用分治法的话,平均时间复杂度为Θ(n lg n)。实际上解决最大子序列问题还有一种更加快速的方法,这种方法的时间复杂度是Θ(n),是一种线性的算法
int maxSubArrayAns(int nums[]){ int i, thisSum = 0, maxSum = 0; for(i = 0; i < MAX_N - 1; i++){ thisSum += nums[i]; if(thisSum > maxSum) maxSum = thisSum; else if(thisSum < 0) thisSum = 0; } return maxSum; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决评论 打赏 举报无用 1
悬赏问题
- ¥15 如何获取烟草零售终端数据
- ¥15 数学建模招标中位数问题
- ¥15 phython路径名过长报错 不知道什么问题
- ¥15 深度学习中模型转换该怎么实现
- ¥15 HLs设计手写数字识别程序编译通不过
- ¥15 Stata外部命令安装问题求帮助!
- ¥15 从键盘随机输入A-H中的一串字符串,用七段数码管方法进行绘制。提交代码及运行截图。
- ¥15 TYPCE母转母,插入认方向
- ¥15 如何用python向钉钉机器人发送可以放大的图片?
- ¥15 matlab(相关搜索:紧聚焦)