分治算法求解最大子序列
【分治算法求解最大子序列】题目：
文章图片
文章图片
文章图片
文章图片
#include
#include
using namespace std;
int max3(int a,int b,int c)
{
if(a& a,int left,int right)
{
if(left==right)
{
if(a[left]>0)
return a[left];
else
return 0;
} int center=(left+right)/2;
int maxLeftSum=maxSumRec(a,left,center);
//对左边分治
int maxRightSum=maxSumRec(a,center+1,right);
//对右边分治 int maxLeftBorderSum=0,leftBorderSum=0;
for(int i=center;
i>=left;
i--)//考虑“穿过中间情形”，故从中间向左边遍历
{
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
} int maxRightBorderSum=0,rightBorderSum=0;
for(int i=center+1;
i<=right;
i++)//考虑“穿过中间情形”，故从中间向右边遍历
{
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
} return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
//三者取最大
}int maxSubSum3(const vector& a)
{
return maxSumRec(a,0,a.size()-1);
}
int main()
{
int n;
cin>>n;
vector v;
for(int i=0;
i>x,v.push_back(x);
}
cout< 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 排序（归并排序）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）