|
<div class="cnblogs_Highlighter">
<pre class="brush:php;gutter:true;">最大子数组问题，股票价格示例：
1.在最高价格开始向左寻找之前的最低价格
2.在最低价格开始向右寻找之后的最高价格
3.暴力求解法，尝试每队可能的买进和卖出组合，保证卖出在买进之后
key
buy
sell
for i=0;i<n;i++
for j=i+1;j<n;j++
p=key=arr[j]-arr[i]
if !key key=p
if key<p buy=i sell=j
问题变化：数组A中元素连续相加最大的子数组，只有当元素有负数时才有意义
分治策略的求解思路：
1.找到数组中的中央位置mid,A[low..mid],A[mid+1..high]
2.A[low,high] 完全位于子数组A[low..mid] low<=i<=j<=mid
3.完全位于A[mid+1..high] mid<i<=j<=hign
4.跨越中点 low<=i<=mid<j<=hign
5.找出左半部分最大和(从中间到左找)，找出右半部分最大和(从中间向右找)
leftSum left
for i=mid;i>=low;i--
sum=sum+A[i]
if sum>leftSum
leftSum=sum
left=i
rightSum right
for j=mid+1;j<=high;j++
sum+=A[j]
if sum > rightSum
rightSum=sum
right=i
6.递归调用
mid=(low+high)/2
find(A,low,mid)
find(A,mid+1,high)
findCross(A,mid,high)
（编辑：安卓应用网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
