《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。

Zedd

《算法导论(第三版)》第四章4.1，使用分治策略求最大子数组问题。

$ e' X9 R2 |. e! @+ u5 @主函数：

• 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)%展示结果
• 
  9 A$ A9 J6 L. `* U7 f/ ~- J+ @

- Q* @! ~; E1 q  h9 w/ \1 a) [
2 X6 ~+ N" C: `, T
递归函数：
; G/ N6 J" \. D& r6 U" y

• 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
• 
  

1 a) c& G/ E8 W' u$ Q* s* }[color=rgb(51, 102, 153) !important]复制代码

" L! @' j% k7 |求解函数：

• 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
• 
  3 O9 b2 Z& d/ T, @1 S* N9 f' Z4 o7 ^' ~

. h' C0 _4 P/ r! `" k- H* C1 n

wu68aq

使用分治策略求最大子数组问题。