算法导论之分治策略：最大子数组问题

逃离我推掉我的手 2022-08-21 00:03 163阅读 0赞

我们先说一下分治策略的基本步骤：首先我们要递归的求解一个问题，在每层的递归中会分为一下三个过程：

分解：将大问题划分为子问题，子问题形同大问题，只是规模更小。

解决：递归的求解出子问题。

合并：将子问题的答案合并为原问题的解。

我们首先介绍实现的算法：

我们要找数组A的最大子数组，那么我们需要把数组A分为规模尽可能相等的两个子数组：数组A\[low..mid\]和数组A\[mid+1..high\]。

接着我们需要找出数组A\[low..mid\]和数组A\[mid+1..high\]中的最大子数组，然后与跨过中点mid（low=<i=<mid<j=<high）的最大子数组的值进行比较。

如果用这个方法那么时间复杂度为：

θ(1) 若n = 1

T(n)  =

2T(n/2) + θ(n)若n>1

我们可以用主方法（master）求递归式的解，也可以用数学归纳法求出。

所以该算法的时间复杂度为：T(n)=θ(nlgn)。

而如果用暴力破解的方法，时间复杂度为：θ(n^2)。

用Java代码实现如下：

package algorithms;
    
    import java.util.ArrayList;
    
    public class FINDMAXIMUMSUBARRAY {
    	ArrayList<Integer> A;
    	int High = 0;
    	int Low = 0;
    	int Max_Left = 0;
    	int Max_Right = 0;
    	int sum = 0;
    
    	public FINDMAXIMUMSUBARRAY(ArrayList<Integer> arrayList, int hight, int low) {
    		A = arrayList;
    		this.Low = low;
    		this.High = hight;
    	}
    	private FINDMAXIMUMSUBARRAY doFind(){
    		if (this.Low == this.High) {
    			this.sum = this.A.get(Low-1);
    			this.Max_Left = this.Low;
    			this.Max_Right = this.High;
    			return this;
    		}
    		else{
    			int mid = (this.High + this.Low)/2;
    			FINDMAXIMUMSUBARRAY FMSL = (new FINDMAXIMUMSUBARRAY(this.A, this.High, mid+1)).doFind();
    			FINDMAXIMUMSUBARRAY FMSR = (new FINDMAXIMUMSUBARRAY(this.A, mid, this.Low)).doFind();
    			FINDMAXIMUMSUBARRAY FMSM = this.doFindCross();
    			if (FMSL.sum > FMSR.sum && FMSL.sum > FMSM.sum) {
    				return FMSL;
    			}else if (FMSR.sum > FMSL.sum && FMSR.sum > FMSM.sum) {
    				return FMSR;
    			}else {
    				return FMSM;
    			}
    		}
    	}
    
    	private FINDMAXIMUMSUBARRAY doFindCross() {
    		FINDMAXIMUMSUBARRAY FC = new FINDMAXIMUMSUBARRAY(A, this.High, this.Low);
    		int mid = (this.High + this.Low)/2;
    		int left_sum= Integer.MIN_VALUE;
    		int sum = 0;
    		for (int i = mid; i >= this.Low; i--) {
    			sum += A.get(i-1);
    			if (sum > left_sum) {
    				left_sum = sum;
    				FC.Max_Left = i;
    			}
    		}
    		int right_sum = Integer.MIN_VALUE;
    		sum = 0;
    		for (int i = mid+1; i <= this.High; i++) {
    			sum += A.get(i-1);
    			if (sum > right_sum) {
    				right_sum = sum;
    				FC.Max_Right = i;
    			}
    		}
    		FC.sum = left_sum  + right_sum;
    		
    		return FC;
    	}
    	public static void main(String[] args) {
    		ArrayList<Integer> arrayList = new ArrayList<Integer>();
    		arrayList.add(13);
    		arrayList.add(-3);
    		arrayList.add(-25);
    		arrayList.add(20);
    		arrayList.add(-3);
    		arrayList.add(-16);
    		arrayList.add(-23);
    		arrayList.add(18);
    		arrayList.add(20);
    		arrayList.add(-7);
    		arrayList.add(12);
    		arrayList.add(-5);
    		arrayList.add(-22);
    		arrayList.add(15);
    		arrayList.add(-4);
    		arrayList.add(7);
    		FINDMAXIMUMSUBARRAY f= new FINDMAXIMUMSUBARRAY(arrayList, arrayList.size(), 1).doFind();
    		for (int i = f.Max_Left; i <= f.Max_Right; i++) {
    			System.out.print(arrayList.get(i-1) + " ");
    			
    		}
    		System.out.println();
    		System.out.println("this is the sum :" + f.sum);
    
    	}
    
    }

求这类问题时候，分治策略不一定都是最好的选择，当我们求斐波那契数列（Fibonacci sequence）的时候，如果给的n过大（比如50），那么程序的执行时间就会很长。

所以用什么方法视情况而定。

参考资料：  
算法导论  
  
备注：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/50810702  
作者：WSYW126