【算法】最大子數組 分治法

前言

去年看的書比較多：java程式設計思想，深入了解Java虛拟機——JVM進階特性與最佳實踐，jvm7的官方說明書，java并發程式設計實踐。程式設計語言看的差不多了，又開始啃程式設計語言運作的環境：Linux作業系統，Linux Kernel Development, 3rd Edition。看了幾章，感覺有點頭腦風暴，雖然大學也學習了作業系統原理，但還是現在收獲比較大，挑戰也比較大，對算法和資料結構有比較高的要求。是以我在看完幾章之後，毅然決然的奔向了算法。通過搜尋引擎找到了：Introduction_To_Algorithms，算法的介紹。名字很親民，但是正統的國内翻譯是 算法導論 。我比較讨厭這樣的翻譯，人家英文明明是算法的介紹，隻要有興趣的人都可以閱讀和了解，而算法導論，我的天啊，是不是研究所學生水準才能看懂。牢騷發完，開始記錄一下。

分治法介紹

第一次看這個，感覺挺高端的，但是看看英文原版 divide-and-conquer ，分解和征服，這樣就比較明确了嘛，将一個問題分解成多個子問題，解決完子問題，再解決原始問題。

使用分治法解決問題的思路

1. 分解：将原始問題分解成若幹個子問題，這些子問題是相同問題小的執行個體。
2. 征服：通過遞歸征服子問題。如果子問題已經足夠的小，那就直截了當的解決這個子問題。
3. 合并：将子問題的解決方案合并成原始問題的解決方案。

最大子數組問題

現在有這麼一個數組，裡面都是整數型（包含負數）,求最大子數組（連續幾個相加最大）。這個問題猛地一看，有點蒙，來看一下使用分治法解決這個問題的思路：

假設我們要在數組A[low,high]中找到最大子數組。分治法給我們的建議是将這個數組盡可能的分解成兩個大小相同的數組。也就是說，我們找到數組A的中間點，定義為 mid，然後我們征服 這兩個子數組：A[low,mid],A[mid+1,high]。我們解釋一下任何一個連續的A[low,high]的子數組A[i,j]必須存在一下這幾個區域：

• 全部在子數組A[low,mid]，即 low<=i<=j<=mid
• 全部在子數組A[mid+1,high]，即 mid<i<=j<=high
• 跨越中間點，即 low<=i<=mid<j<=high

是以，數組A的最大子數組必須在以上的三個位置之一。實時上，A[low,high]的最大子數組一定是 這三種情況下最大子數組的和最大值。我們可以遞歸的找到A[low..mid]和A[mid+1..high]子數組，因為這些問題是尋找最大子數組問題小的執行個體。剩下的問題就是找到跨越中間點的最大子數組，最後，比較這三種情況和的最大值，最大的就是我們要找的最終答案。

跨越中間點的最大子數組

我們可以很快的找到跨越中間點最大子數組，時間複雜度時O(n)。這個問題不能通過遞歸的方式來解決，因為它增加了限制：最大子數組必須跨越中心點。是以它不是比原始問題小的執行個體。任何一個跨越中間點的子數組都是由這兩個子數組A[i..mid]A[mid+1..j]組成 ，其中 low<=i<=mid,mid<j<=high。是以我們隻需要找到找到形如：A[i..mid] 和A[mid+1..j]的最大子數組，然後将他們合并即可解決這個問題。FIND-MAX-CROSSING-SUBARRAY這個方法的輸入參數有：數組 A，索引low,mid,high，這個方法的輸出是一個數組，這個數組包含劃分跨越中間點的最大子數組的兩個索引位置，還有這個最大子數組的和。現在貼上java代碼：

static Integer[] findMaxCrossingSubArr(Integer[] arr,Integer low,Integer mid,Integer high) {
		int left_sum=Integer.MIN_VALUE;
		int sum=0;
		int maxLeft=mid;
		for(int i=mid;i>=low;i--) {
			sum=sum+arr[i];
			if(sum>left_sum) {
				left_sum=sum;
				maxLeft=i;
			}
		}
		
		int right_sum=Integer.MIN_VALUE;
		sum=0;
		int maxRight=mid+1;
		for (int j=mid+1;j<=high;j++) {
			sum=sum+arr[j];
			if (sum>right_sum) {
				right_sum=sum;
				maxRight=j;
			}
		}
		Integer[] res= {maxLeft,maxRight,left_sum+right_sum};
		return res;
	}
           

然後使用貼出分治法的主方法

static Integer[] findMaxSubArr(Integer[] arr,Integer low,Integer high) {
		if (low==high) {
			Integer[] _arr= {low,high,arr[low]};
			return _arr;
		}
		Integer mid=(low + high)>>1;
		Integer left[]=new Integer[3];
		Integer right[]=new Integer[3];
		Integer crossing[]=new Integer[3];
		left=findMaxSubArr(arr, low, mid);
		right=findMaxSubArr(arr, mid+1, high);
		crossing=findMaxCrossingSubArr(arr, low, mid, high);
		if (left[2]>=right[2]&&left[2]>=crossing[2]) {
			return left;
		}
		if (right[2]>=left[2]&&right[2]>=crossing[2]) {
			return right;
		}
		return crossing;
	}
           

後記

看算法導論的過程真的很苦逼，對數學的要求也比較高，一步一個腳印的走下去把...

轉載于:https://my.oschina.net/huaxiaoqiang/blog/3012558