首页 > 代码库 > 分治法求最大子序列
分治法求最大子序列
给定一个序列,下标为 i, i+1, i+2, ...... , j,设 mid = (i+j)/2, 则最大子序列可能出现的地方有三个,mid的左边,mid的右边,或者在中间(包括mid)。只要求出左边和右边的最大子序列(子问题),和边界上左边和右边最大子序列的和,找出三个子序列中最大的即可。
#include <iostream> using namespace std; /*分治法解决最大子序列问题*/ int MaxSubSum(const int a[], int left, int right); int main(){ freopen("input.txt", "r", stdin); int a[100]; int num; int length = 0; while(cin >> num){ a[length++] = num; } cout << MaxSubSum(a, 0, length-1) << endl; } int MaxSubSum(const int a[], int left, int right){ int maxLeftSum, maxRightSum; int maxLeftBorderSum = 0, maxRightBorderSum = 0; int leftBorderSum = 0, rightBorderSum = 0; int center = (left + right)/2; //基准情况 if(left == right){ if(a[left] > 0) return a[left]; else return 0; } //递归调用子序列(进行分治) maxLeftSum = MaxSubSum(a, left, center); maxRightSum = MaxSubSum(a, center+1, right); //跨越中间的最长子序列和 for(int i=center; i>=left; i--){ leftBorderSum += a[i]; if(leftBorderSum > maxLeftBorderSum){ maxLeftBorderSum = leftBorderSum; } } for(int i=center+1; i<=right; i++){ rightBorderSum += a[i]; if(rightBorderSum > maxRightBorderSum){ maxRightBorderSum = rightBorderSum; } } //求出这三种情况下最大的 return max(max(maxLeftSum, maxRightSum), (maxLeftBorderSum + maxRightBorderSum)); }
时间复杂度为 O(NlogN)
分治法求最大子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。