|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。8 [6 ]/ @! D% N9 ~5 A# E8 |1 U0 D# Y
% E% ?2 j4 `+ x- ~4 d/ Y主函数：! n- I) F6 Q/ h6 b' s& y; J3 b
- 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)%展示结果
# c! k% W! J7 x5 {3 e- s) k
: g1 b" ~; m8 C7 r1 P) a5 u* P. G" O8 N! M W3 @' \
. S* E- p5 }- j0 g. Z& E* E2 [
递归函数：
9 N, R5 g7 }# C0 N' i) r9 X- 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
7 u% g* [3 l: m/ n$ a0 A
: D$ Y$ R+ p) L5 A6 T
[color=rgb(51, 102, 153) !important]复制代码6 ]$ h& G7 R: M, Q: ^% b
9 ]2 S1 _8 _, L/ n7 @
求解函数：8 W/ R$ ?8 U" X) `8 Q4 E
- 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
- , X) g8 u6 j* }7 V! O) S: D- ~( s
; `( @# s! [/ w2 R7 S9 ?2 _0 t. Q' o
3 X6 _ h( v9 g. K
|
|
/1 
发表于 2020-3-11 11:20
收藏
淘帖
支持！
反对！