用分治方法实现查找最大连续子数组 java代码实现

- 日理万妓 2022-04-08 09:16 102阅读 0赞

### 学习历程 ###

今天在看算法导论的时候，看见这样一个算法，权当记录下我的学习过程。  
问题是求解一个数组中和最大的连续数组。这个数组如下所示  
\[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7\]  
这个最大连续的子数组是 \[18, 20, -7, 12\]

**用算法来解决这样一个通用的问题，该怎么设计算法呢？**

### 一. 将数组中的元素排列组合 ###

如果将全部的组合方式的和进行比较，算法的复杂度就为 O(n^2)。代价极高

### 二. 使用分治方法 ###

我们可以换种想法，将数组分成两半，那么最大子数组所在的位置有三种  
**1.在左半边数组**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70]  
**2.在右半数组**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 1]  
**3.左边有一部分，右边也有一部分**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 2]  
额，那么大家一定有疑问了，得出最大子数组的位置有什么意义呢？  
这就是伟大的分治策略呀，把数组砍成两半，我只需找到左数组、右边数组的最大子数组与脚踏两只船的最大子数组，然后比较他们三个谁大谁小，就可以求出谁是最大子数组了。

#### 先说跨越两个数组的最大子数组怎么求 ####

先求左数组从右往左的最大累加值，再求右边数组从左往右的最大累加值，然后把这两部分加起来，就是最大子数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 3]

/**
         * 求出该数组索引在 low 到 high 中的元素的最大子数组，
         * 子数组必须跨越索引为 mid 的元素，即包含索引为 mid 的元素
         * @param arr
         * @param low
         * @param mid
         * @param high
         * @return int 数组，长度为3。第一个元素为最大子数组的左边索引，
         * 		   第二个为右边索引，第三个为和。
         */
        public static int[] findMaxCrossingSubarray (int[] arr, int low, int mid, int high) {
        	// 左边数组最大子数组的和，0x80000000是 int 所能表示的最小值
        	int leftSum = 0x80000000;
        	// 左边数组累加的和
        	int sum = 0;
        	int maxLeft = mid;
        	// 遍历左数组
        	for (int i = mid; i >= low; i--) {
        		sum += arr[i];
        		// 如果累加的和大于最大子数组的和，则替换最大子数组
        		if (sum > leftSum) {
        			// 最大子数组左边的索引
        			maxLeft = i;
        			// 替换左边最大子数组的和
        			leftSum = sum;
        		}
        	}
        	// 右边数组最大子数组的和，0x80000000是 int 所能表示的最小值
        	int rightSum = 0x80000000;
        	// 右边数组累加的和
        	sum = 0;
        	int maxRight = mid + 1;
        	for (int i = mid + 1; i <= high; i++) {
        		sum += arr[i];
        		// 如果累加的和大于最大子数组的和，则替换最大子数组
        		if (sum > rightSum) {
        			// 最大子数组右边的索引
        			maxRight = i;
        			// 替换右边最大子数组的和
        			rightSum = sum;
        		}
        	}
        	return new int[] { maxLeft, maxRight, leftSum + rightSum };
        }

#### 既然我们求出了跨越两个数组的最大子数组，接下来就是求左右两个数组的最大子数组了。 ####

求左边元素的最大子数组，我们还是需要求三个东西  
首先，把左数组砍成两半，求左数组与右数组的最大子数组，还有再求一个跨越两个数组的子数组，然后求出这三个子数组谁大，谁大谁就是我们要求的最大子数组。  
右边也是这样

于是问题的规模被减小了。

当数组被分到只有一个元素的时候，就不需要再分了，因为最大子元素就是它本身。

于是乎，求左右数组的最大子数组的问题就这样被一分再分，直至不能再分，然后左右子数组就稀里糊涂的被求出来了。然后我们在一层层往上回去，直至到达最顶层，左右子数组被求出来。

然后，贴上我们的递归代码吧，要用到上面的函数哦。

/**
     * 求出该数组索引在 low 到 high 中的元素的最大子数组
     * @param arr
     * @param low
     * @param high
     * @return int 数组，长度为3。第一个元素为最大子数组的左边索引，
     *         第二个为右边索引，第三个为和。
     */
    public static int[] findMaximumSubarray (int[] arr, int low, int high) {
    	// 此时只有一个元素，最大子元素就是它本身
    	if (low == high) return new int[] { low, high, arr[low] };
    	
    	// 中间数
    	int mid = (low + high) / 2;
    	
    	// 求得左边数组的最大子数组
    	int[] leftMax = findMaximumSubarray(arr, low, mid);
    	// 求得右边数组的最大子数组
    	int[] rightMax = findMaximumSubarray(arr, mid + 1, high);
    	// 求得跨越中点的最大子数组
    	int[] crossMax = findMaxCrossingSubarray(arr, low, mid, high);
    	
    	// 比较这三个子数组的和的大小
    	if (leftMax[2] >= rightMax[2] && leftMax[2] >= crossMax[2]) {
    		// 左边子数组最大
    		return leftMax;
    	} else if (rightMax[2] >= leftMax[2] && rightMax[2] >= crossMax[2]) {
    		// 右边子数组最大
    		return rightMax;
    	} else {
    		// 跨越中点的子数组最大
    		return crossMax;
    	}
    }

接下来，奉上一个测试方法

@Test
    public void testFindMaximumSubarray () {
    	int[] arr = new int[] { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
    	int[] max = findMaximumSubarray(arr, 0, arr.length - 1);
    	//  打印最大子数组
    	for(int i = max[0]; i <= max[1]; i++) {
    		// 打印每个元素
    		System.out.print(arr[i] + ", ");
    	}
    	System.out.println();
    	// 打印最大子元素的和
    	System.out.println("和为：" + max[2]);
    }

结果为：  
![在这里插入图片描述][20181207162333110.png]  
顺便补上一句，时间复杂度只有O(n\*lgn)哦  
大家到这里是否对 `0x8000000` 是最小的 int 数有疑问呢？不妨看看这篇博客。  
[https://blog.csdn.net/youyou362/article/details/72667951/][https_blog.csdn.net_youyou362_article_details_72667951]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70]: /images/20220407/2e9b9002c4a9424dba3f3bfa920b7f6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 1]: /images/20220407/ea3d20a5eda4404c8a5315de30a9614d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 2]: /images/20220407/c1c5a94ec7fd43608b265ec966c93b9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTU4NDM2_size_16_color_FFFFFF_t_70 3]: /images/20220407/e63ff32d5e8d41d2b96a8bed7532b2ba.png
[20181207162333110.png]: /images/20220407/44dbaf2cbb3941a2bd9681012041b146.png
[https_blog.csdn.net_youyou362_article_details_72667951]: https://blog.csdn.net/youyou362/article/details/72667951/