EDA365电子论坛网
标题:
《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。
[打印本页]
作者:
Zedd
时间:
2020-3-11 11:20
标题:
《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。
《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。
2 Z% h( g8 H( d, H7 H. m7 r
& |5 y* d$ Q0 J. J* `4 C. k0 o! `
主函数：
& g& e: a3 `2 s% m- n$ P
clear;clc
A=[13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7];%例 源数组
[low,high,sum1]=FIND_MAXIMUM_SUBARRAY(A,1,length(A))%求解
A(low:high)%展示结果
. p- k3 V6 h' o/ _
K2 x7 l# a& A- o9 q
# ~: G2 O. F# B" S8 B. h4 Q9 a; h2 W
1 o! x' T; s6 S x2 n
递归函数：
7 u% j v; H# E
function [low,high,sum1] = FIND_MAXIMUM_SUBARRAY(A,low,high)
%输入，[源数组，左边界，右边界]
%输出，[左边界，右边界，边界内最大子数组的和]
if low==high %两侧仅剩单个数值时，直接返回数字
sum1=A(low);
else %如果不是单个数字，则进行递归分解成三部分
mid=floor((low+high)/2);%定义中间值
[left_low,left_high,left_sum]=FIND_MAXIMUM_SUBARRAY(A,low,mid);%分解左子数组，并求子数组的值
[right_low,right_high,right_sum]=FIND_MAXIMUM_SUBARRAY(A,mid+1,high);%分解右子数组，并求子数组的值
[cross_low,cross_high,cross_sum]=FIND_MAX_CROSSING_SUBARRAY(A,low,mid,high);%求出跨界子数组的值
%将三种结果做比较，返回最大的情况
low=[left_low,right_low,cross_low];
high=[left_high,right_high,cross_high];
sum1=[left_sum,right_sum,cross_sum];
[sum1,addr]=max([left_sum,right_sum,cross_sum]);%
low=low(addr);
high=high(addr);
end
end
0 a/ a; y' Q; _
" X* l; O. Y* L; B! | k* W, `
[color=rgb(51, 102, 153) !important]
复制代码
4 ]- V- w+ o7 k6 r. I& c3 [
6 C% w4 q( x# }- L) O) [- d
求解函数：
. G6 Z. W. C7 Q# T* b$ N
function [max_left,max_right,sum3] = FIND_MAX_CROSSING_SUBARRAY(A,low,mid,high)
%求左侧的最大子数组
left_sum=-inf;%最大子数组的和
sum1=0;%子数组和的累计
for i=mid:-1:low%序数
sum1=sum1+A(i);%累计
if sum1>left_sum%判断最大子数组
left_sum=sum1;%最大子数组的值
max_left=i;%最大子数组的左侧截止位置
end
end
%求右侧的最大子数组
right_sum=-inf;%最大子数组的和
sum2=0;%子数组和的累计
for j=mid+1:high
sum2=sum2+A(j);
if sum2>right_sum
right_sum=sum2;
max_right=j;%最大子数组的右侧截止位置
end
end
sum3=left_sum+right_sum;%两侧最大子数组之和
end
: R2 Z; z' N. V6 b1 L. S
+ R& E: s4 h" ?% H, Q9 x! V3 Y
+ T: m: y1 w* H7 Q
) ~& z# k8 `" q* \# d2 L- q
作者:
wu68aq
时间:
2020-3-11 16:49
使用分治策略求最大子数组问题。
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2