Algorithm —— 最大子数组求解（五）

最新推荐文章于 2022-08-12 23:12:48 发布
最新推荐文章于 2022-08-12 23:12:48 发布
阅读量252 收藏
点赞数
分类专栏： Algorithms 文章标签： 算法导论 算法 最大子数组 分治思想
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/csdn_of_coder/article/details/79953729
版权
本文介绍了一种利用分治策略解决最大子数组问题的方法。通过递归地将问题分解为子问题，并寻找跨越中点的最大子数组，最终合并结果得出答案。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

Algorithm —— 最大子数组求解


《算法导论》中引出了一个求某个数组的和最大子数组问题：在原数组A中，求一个子数组a,它的各元素值的和是A的各个子数组中最大的；且子数组a的各元素下标值要连续。

要注意的是，如果要求某个数组的最大子数组，则此数组中的值必须要包含负值；否则，求最大子数组是没有意义的，因为此时，整个数组的和肯定是最大的，就不必再求了。

我们使用分治策略来解决该问题。假定我们要寻找数组A[low...high]的最大子数组，因为要使用分治技术，这也就意味着我们要将数组A划分为两个规模尽量相等的子数组。也就是找到数组A的中央位置mid，然后考虑求解两个子数组A[low...mid]和A[mid+1...high]。

我们可以知道，数组A[low...high]的任何连续子数组A[i...j]所处的位置必然是一下三种情况之一：

  1. 完全位于子数组A[low...mid]中，因此low =< i =< j =< mid；子数组完全位于A[low...mid]中。
  2. 完全位于子数组A[mid+1...high]中，因此mid < i =<j =< high；子数组完全位于A[mid+1...high]中。
  3. 跨越了中点mid，因此lwo =< i =< mid < j =< high；子数组跨越了中点mid。


因此，A[low...high]的一个最大子数组所处的位置必然是上述三种情况之一。对于前两种情况，我们可以递归求解，因为 这两个问题仍是最大子数组问题，只是规模更小；剩下的工作就是寻找跨越中点的最大子数组。所以问题的最终结果就是在三种情况中选取和最大者。

寻找跨越中点的最大子数组问题并不是原问题规模更小的实例，因为它加入了限制——求出的子数组必须跨越中点。任何跨越中点的子数组都由两个子数组A[i...mid]和A[mid+1...j]组成，其中low =< i =< mid < j =< high。因此，我们只需找出形如A[i...mid]和A[mid+1...j]的最大子数组，然后将其合并即可。此问题的函数如下所示：

	/**
	 * 
	 * @author coder
	 * 
	 *         代表'和最大子数组'信息的封装类型
	 * 
	 */
	private class MaxSumSubArray {

		public MaxSumSubArray(int left_index, int right_index, int sum) {
			this.left_index = left_index;
			this.right_index = right_index;
			this.sum = sum;
		}

		int left_index;// 数组的左下标边界值
		int right_index;// 数组的右下标边界值
		int sum;// 此子数组各元素的和值

		@Override
		public String toString() {
			return "MaxSumSubArray [left_index=" + left_index + ", right_index=" + right_index + ", sum=" + sum + "]";
		}
	}

	/**
	 * 返回一个跨越中点的'和最大子数组'的边界,及此数组中所有值的和;因为要寻找的'和最大子数组'下标必须要跨越中点,所以该子数组的下标范围一定是从中点向左右两边延伸、且连续;
	 * 
	 * 对于左数组,我们只需在下标范围[low...mid]中,从mid值开始由右向左依次计算各元素相加的和,并逐一比较各次所得和的大小;记录当前得到的最大的和与此时运算的数组下标值i;循环结束后,就得到了这个和最大子数组的左半部分a[i...mid]
	 * 对于右数组,也是类似,从(mid+1)开始,从左向右遍历计算各元素相加的和;得到当前最大的和值时的下标j;循环结束后,就得到这个子数组的右半部分b[mid+1...high]
	 * 
	 * 合并子数组a/b,就得到了当前跨越中点的'和最大子数组'c[i...j];
	 * 
	 * @param array
	 *            当前需要处理的数组
	 * @param low
	 *            在当前数组中需要处理的子数组的下标左边界
	 * @param mid
	 *            在当前数子组中需要处理的下标范围对应的下标中点
	 * @param heigh
	 *            在当前数组中需要处理的子数组的下标右边界
	 * @return 返回一个MaxSumSubArray实例,即 跨越中点的'和最大子数组'的封装对象
	 */
	private MaxSumSubArray findMaxCrossingSubArray(int[] array, int low, int mid, int high) {

		int left_sum = 0;// 记录每次左边找到的最大和值
		int sum = 0; // 记录左边子数组所有元素的和值
		int max_left = -1;// 记录每次找到左边子数组最大和值时的下标值

		for (int i = mid; i >= low; i--) {
			sum = sum + array[i];
			if (sum > left_sum) {
				left_sum = sum;
				max_left = i;
			}
		}

		int right_sum = 0;// 记录每次右边找到的最大和值
		sum = 0; 记录右边子数组所有元素的和值
		int max_right = -1;// 记录每次找到右边子数组最大和值时的下标值

		for (int j = mid + 1; j <= high; j++) {
			sum = sum + array[j];
			if (sum > right_sum) {
				right_sum = sum;
				max_right = j;
			}
		}

		MaxSumSubArray obj = new MaxSumSubArray(max_left, max_right, left_sum + right_sum);

		return obj;

	}
此时，我们就解出了求跨越中点的最大子数组问题；又由于前两种情况是原问题规模更小的实例，可用递归求解；所以此时求数组A[low...high]的最大子数组问题的解如下： 

	/**
	 * 
	 * @author coder
	 * 
	 *         代表'和最大子数组'信息的封装类型
	 * 
	 */
	private class MaxSumSubArray {

		public MaxSumSubArray(int left_index, int right_index, int sum) {
			this.left_index = left_index;
			this.right_index = right_index;
			this.sum = sum;
		}

		int left_index;// 数组的左下标边界值
		int right_index;// 数组的右下标边界值
		int sum;// 此子数组各元素的和值

		@Override
		public String toString() {
			return "MaxSumSubArray [left_index=" + left_index + ", right_index=" + right_index + ", sum=" + sum + "]";
		}
	}

	/**
	 * 找到目标数组array的一个'和最大子数组',并返回该'和最大子数组'的下标及所有元素和信息
	 * 
	 * @param array
	 *            目标源数组
	 * @param low
	 *            需要操作的子数组的下标左边界
	 * @param high
	 *            需要操作的子数组的下标右边界
	 * @return 返回从目标值数组中指定的子数组c[low...high]的'和最大子数组'信息
	 */
	public MaxSumSubArray findMaxImumSubArray(int[] array, int low, int high) {

		if (low > high || array == null) {
			throw new IllegalArgumentException("findMaxImumSubArray Argument is illegal!");
		}

		if (high == low) {
			return new MaxSumSubArray(low, high, array[low]);
		}

		int mid = (low + high) / 2;

		MaxSumSubArray leftMaxSSArray = findMaxImumSubArray(array, low, mid);
		MaxSumSubArray rightMaxSSArray = findMaxImumSubArray(array, mid + 1, high);
		MaxSumSubArray crossMidMaxSSArray = findMaxCrossingSubArray(array, low, mid, high);

		if (leftMaxSSArray.sum >= rightMaxSSArray.sum && leftMaxSSArray.sum >= crossMidMaxSSArray.sum)
			return leftMaxSSArray;
		else if (rightMaxSSArray.sum >= leftMaxSSArray.sum && rightMaxSSArray.sum >= crossMidMaxSSArray.sum)
			return rightMaxSSArray;

		return crossMidMaxSSArray;
	}

	/**
	 * 返回一个跨越中点的'和最大子数组'的边界,及此数组中所有值的和;因为要寻找的'和最大子数组'下标必须要跨越中点,所以该子数组的下标范围一定是从中点向左右两边延伸、且连续;
	 * 
	 * 对于左数组,我们只需在下标范围[low...mid]中,从mid值开始由右向左依次计算各元素相加的和,并逐一比较各次所得和的大小;记录当前得到的最大的和与此时运算的数组下标值i;循环结束后,就得到了这个和最大子数组的左半部分a[i...mid]
	 * 对于右数组,也是类似,从(mid+1)开始,从左向右遍历计算各元素相加的和;得到当前最大的和值时的下标j;循环结束后,就得到这个子数组的右半部分b[mid+1...high]
	 * 
	 * 合并子数组a/b,就得到了当前跨越中点的'和最大子数组'c[i...j];
	 * 
	 * @param array
	 *            当前需要处理的数组
	 * @param low
	 *            在当前数组中需要处理的子数组的下标左边界
	 * @param mid
	 *            在当前数子组中需要处理的下标范围对应的下标中点
	 * @param heigh
	 *            在当前数组中需要处理的子数组的下标右边界
	 * @return 返回一个MaxSumSubArray实例,即 跨越中点的'和最大子数组'的封装对象
	 */
	private MaxSumSubArray findMaxCrossingSubArray(int[] array, int low, int mid, int high) {

		int left_sum = 0;// 记录每次左边找到的最大和值
		int sum = 0; // 记录左边子数组所有元素的和值
		int max_left = -1;// 记录每次找到左边子数组最大和值时的下标值

		for (int i = mid; i >= low; i--) {
			sum = sum + array[i];
			if (sum > left_sum) {
				left_sum = sum;
				max_left = i;
			}
		}

		int right_sum = 0;// 记录每次右边找到的最大和值
		sum = 0; 记录右边子数组所有元素的和值
		int max_right = -1;// 记录每次找到右边子数组最大和值时的下标值

		for (int j = mid + 1; j <= high; j++) {
			sum = sum + array[j];
			if (sum > right_sum) {
				right_sum = sum;
				max_right = j;
			}
		}

		MaxSumSubArray obj = new MaxSumSubArray(max_left, max_right, left_sum + right_sum);

		return obj;

	}
完整的测试代码如下： 

public class AlgorithmTest {

	public static void main(String[] args) {
		int[] array = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
		AlgorithmTest algorithm = new AlgorithmTest();
		MaxSumSubArray res = algorithm.findMaxImumSubArray(array, 0, array.length - 1);
		System.out.println(res);
	}

	/**
	 * 
	 * @author coder
	 * 
	 *         代表'和最大子数组'信息的封装类型
	 * 
	 */
	private class MaxSumSubArray {

		public MaxSumSubArray(int left_index, int right_index, int sum) {
			this.left_index = left_index;
			this.right_index = right_index;
			this.sum = sum;
		}

		int left_index;// 数组的左下标边界值
		int right_index;// 数组的右下标边界值
		int sum;// 此子数组各元素的和值

		@Override
		public String toString() {
			return "MaxSumSubArray [left_index=" + left_index + ", right_index=" + right_index + ", sum=" + sum + "]";
		}
	}

	/**
	 * 找到目标数组array的一个'和最大子数组',并返回该'和最大子数组'的下标及所有元素和信息
	 * 
	 * @param array
	 *            目标源数组
	 * @param low
	 *            需要操作的子数组的下标左边界
	 * @param high
	 *            需要操作的子数组的下标右边界
	 * @return 返回从目标值数组中指定的子数组c[low...high]的'和最大子数组'信息
	 */
	public MaxSumSubArray findMaxImumSubArray(int[] array, int low, int high) {

		if (low > high || array == null) {
			throw new IllegalArgumentException("findMaxImumSubArray Argument is illegal!");
		}

		if (high == low) {
			return new MaxSumSubArray(low, high, array[low]);
		}

		int mid = (low + high) / 2;

		MaxSumSubArray leftMaxSSArray = findMaxImumSubArray(array, low, mid);
		MaxSumSubArray rightMaxSSArray = findMaxImumSubArray(array, mid + 1, high);
		MaxSumSubArray crossMidMaxSSArray = findMaxCrossingSubArray(array, low, mid, high);

		if (leftMaxSSArray.sum >= rightMaxSSArray.sum && leftMaxSSArray.sum >= crossMidMaxSSArray.sum)
			return leftMaxSSArray;
		else if (rightMaxSSArray.sum >= leftMaxSSArray.sum && rightMaxSSArray.sum >= crossMidMaxSSArray.sum)
			return rightMaxSSArray;

		return crossMidMaxSSArray;
	}

	/**
	 * 返回一个跨越中点的'和最大子数组'的边界,及此数组中所有值的和;因为要寻找的'和最大子数组'下标必须要跨越中点,所以该子数组的下标范围一定是从中点向左右两边延伸、且连续;
	 * 
	 * 对于左数组,我们只需在下标范围[low...mid]中,从mid值开始由右向左依次计算各元素相加的和,并逐一比较各次所得和的大小;记录当前得到的最大的和与此时运算的数组下标值i;循环结束后,就得到了这个和最大子数组的左半部分a[i...mid]
	 * 对于右数组,也是类似,从(mid+1)开始,从左向右遍历计算各元素相加的和;得到当前最大的和值时的下标j;循环结束后,就得到这个子数组的右半部分b[mid+1...high]
	 * 
	 * 合并子数组a/b,就得到了当前跨越中点的'和最大子数组'c[i...j];
	 * 
	 * @param array
	 *            当前需要处理的数组
	 * @param low
	 *            在当前数组中需要处理的子数组的下标左边界
	 * @param mid
	 *            在当前数子组中需要处理的下标范围对应的下标中点
	 * @param heigh
	 *            在当前数组中需要处理的子数组的下标右边界
	 * @return 返回一个MaxSumSubArray实例,即 跨越中点的'和最大子数组'的封装对象
	 */
	private MaxSumSubArray findMaxCrossingSubArray(int[] array, int low, int mid, int high) {

		int left_sum = 0;// 记录每次左边找到的最大和值
		int sum = 0; // 记录左边子数组所有元素的和值
		int max_left = -1;// 记录每次找到左边子数组最大和值时的下标值

		for (int i = mid; i >= low; i--) {
			sum = sum + array[i];
			if (sum > left_sum) {
				left_sum = sum;
				max_left = i;
			}
		}

		int right_sum = 0;// 记录每次右边找到的最大和值
		sum = 0; 记录右边子数组所有元素的和值
		int max_right = -1;// 记录每次找到右边子数组最大和值时的下标值

		for (int j = mid + 1; j <= high; j++) {
			sum = sum + array[j];
			if (sum > right_sum) {
				right_sum = sum;
				max_right = j;
			}
		}

		MaxSumSubArray obj = new MaxSumSubArray(max_left, max_right, left_sum + right_sum);

		return obj;

	}

	public void arrayPrint(int[] array) {
		System.out.print("[");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ", ");
		}
		System.out.println("]");
	}
}
输出如下： 

MaxSumSubArray [left_index=7, right_index=10, sum=43]

求数组的最大子数组问题就解决了。













算法导论--寻找最大子数组
l1024049542的博客
01-19 545
写在前面这是我的第一篇博客； 人总是需要变的，向上地变，不然就完了； ——-引自我的一位导师； 问题求最大子数组 分析 第一种 暴力求解 Θ(n2)Θ(n^2) 此种方法通过两层循环，去寻找最大子数组，思路上很清晰，以i序列的数为起点，求此后的各个子序列的和
算法：动态规划——线性DP（C++)
m0_52530677的博客
04-14 1681
动态规划概述几类典型问题1.最大连续子序列和2.最长不下降子序列3.最长公共子序列4.最长回文子串5.DAG最长路径6.背包问题总结 博客主要参考书：胡凡《算法笔记》 概述 在我看来动态规划就是将一个问题的最优问题分解为子问题的最优解来获得真正的最优解。动态规划问题当中重要的就是： 状态的转化方程：目标态=F（某一状态）。 有边界状态和其值 使用条件：1.有重复的子问题；2.有最优子结构 几类典型问题 1.最大连续子序列和 题目：给定一个序列：S1，S2，S3…Sn，有i,j使得sum=Si+Si+
寻找数组中的最大值算法
colorfulSnow的博客
05-09 755
在右边的大数组中包含了4个小数组，请分别找到每个小数组中的最大值，然后把它们串联起来，形成一个新的数组。 function getMax(tmp){ tmp.sort((a,b)=>{ if(a > b) return -1; if(a < b) return 1; if(a = b) return 0; }) return tmp[0] } function largestOfFour(arr) { // You can do...
一个数组的求解
francis926的专栏
07-27 383
这个是一个数组任意位的求解，今天是看到一个博客上的问题，自己做的尝试，写得不好，其中的n是实际数组的n+1位public decimal sum(int n) //将原数组变形，第一个数分出去，后面构成一个数组， //那么此时的第n位在原数组中应该是第n+1位 {
Algorithm - 求连续子数组的最大和
xsj1987的专栏
10-15 333
1. 如下例程： /* 求连续子数组的最大和 */ int max_sum(int a[], size_t length) { /* 参数合法性检查 */ if (NULL == a || 0 == length) { return 0; } /* 计算连续子数组的最大和 */ size_t i; int max = 0x8
数组常用解题方法（持续更新）
muyu_muyu的博客
10-24 349
1.假设题意是叫你在排序数组中寻找是否存在一个目标值，那么训练有素的读者肯定立马就能想到利用二分法在 O(log⁡n)的时间内找到是否存在目标值。 2.后续继续总结…
数组解题方法总结(持续更新~~~)
qq_43751200的博客
05-11 208
二分方法： 704.二分查找法 35.搜索插入位置 34.在排序数组中查找元素的第一个和最后一个位置 69.x 的平方根 367.有效的完全平方数 双指针方法： 26.删除排序数组中的重复项 283.移动零 844.比较含退格的字符串 977.有序数组的平方 滑动窗口： 209.长度最小的子数组 904.水果成篮 76.最小覆盖子串 模拟行为： 54.螺旋矩阵 59.螺旋矩阵Ⅱ 剑指Offer 29.顺时针打印矩阵 ...
Java-Leetcode-最大子数的和.zip
02-08
这个问题是动态规划的经典例子，它被称为“最大子数组和”或“Kadane's Algorithm”。在Java中，我们通常会创建一个方法来解决这个问题，例如： ```java public int maxSubArray(int[] nums) { int maxSoFar = ...
最大子序列求和问题时间复杂度最优
02-23
### 最大子序列求和问题的最优时间复杂度算法 对于最大子序列求和问题，存在多种解决方法，每种方法具有不同的时间和空间复杂度。分治法是一种有效的方法之一，在处理该类问题时能够达到较优的时间性能。 通过采用...
dynamic programming algorithm
03-08
为了更好地理解如何实现动态规划，在这里提供了一个经典的例子——最大子数组和问题(Maximum Subarray Problem)，该问题是寻找给定整数数组中的连续子数组，使其元素之和最大[^2]。 ```python def max_sub_array...
原地数组求解例题汇总（C++力扣）
weixin_45479946的博客
12-05 264
283.移出0 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 首先确立思想，既然不能使用额外空间，那就使用两个指针。关注点在,不为零的情况下的操作，一旦不为0，就把该元素赋给以k为指针的下标数组中。最后把多余的空间单独放成0。 class Solution { public: void moveZeroes
趣味问题 约瑟夫圈的数组求解方法
rocky_56X的博客
02-02 456
假设n个人围成一个圈，从1开始报数，到3就把报数的人踢出，然后从1开始，一直循环下去，直到最后一个人，请问这个 人是第几号人？ 这就是约瑟夫圈问题，这个问题的求解方法比较多，今天介绍一下它的数组求解方法。 1#include 2 int main() 3 { 4 int num = 0，out = 0,i = 0,n; //num为报号，到3清零；ou
用algorithm库对数组进行简单操作（第二期）
m0_72608151的博客
08-12 319
再次详细介绍了algorithm库对数组进行简易操作的函数使用方法。
【无标题】用algorithm库实现数组查找，排序（第一期）
m0_72608151的博客
08-08 190
简单的algorithm库函数调用，可以方便大程序中基础函数的书写过程。
next数组求解详解
热门推荐
BlackSky's Blog
08-20 5万+
next数组求解详解，以串'ababaaababaa'为例
C++:algorithm常用函数
pzjdsg666的博客
06-01 4221
C++网址：www.clpusplus.com algorithm是C++一个常用的头文件，译为“算法”，其中有几个常用库函数。
nextval数组如何求解
Jeaten
10-08 1万+
求解示例
最大子数组py
最新发布
03-13
### Kadane's Algorithm 的 Python 实现 Kadane's Algorithm 是一种高效的动态规划算法，用于解决最大子数组和问题。以下是基于此算法的 Python 实现代码： ```python def kadanes_algorithm(nums): max_current = max_global = nums[0] # 初始化当前最大值和全局最大值为第一个元素[^1] for i in range(1, len(nums)): # 遍历数组中的每一个元素 max_current = max(nums[i], max_current + nums[i]) # 更新当前最大值 if max_current > max_global: # 如果当前最大值大于全局最大值，则更新全局最大值 max_global = max_current return max_global # 返回最终的最大子数组和 ``` 上述代码的核心逻辑在于每次迭代时计算两个变量 `max_current` 和 `max_global`： - `max_current` 表示以当前位置结尾的最大子数组和。 - `max_global` 记录整个过程中遇到过的最大子数组和。 #### 时间复杂度分析 该算法的时间复杂度为 \(O(n)\)，其中 \(n\) 是输入数组的长度。这是因为它仅需一次遍历来完成所有必要的计算[^2]。 #### 边界情况处理 如果输入数组为空或者只包含负数的情况，可以稍作修改来适应这些边界条件。例如，当数组全为负数时，返回最大的单个元素即可。 ```python def kadanes_algorithm_with_negatives(nums): if not nums: # 处理空数组的情况 return 0 max_current = max_global = nums[0] for num in nums[1:]: max_current = max(num, max_current + num) max_global = max(max_global, max_current) return max_global ``` 以上代码能够正确处理含有负数的数组，并且依然保持线性时间复杂度。 --- ### 示例运行 假设有一个测试用例如下所示： ```python nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] result = kadanes_algorithm(nums) print(result) # 输出应为6，对应于子数组 [4, -1, 2, 1] ``` 在这个例子中，程序会找到连续子数组 `[4, -1, 2, 1]` 并输出其总和为 6。 ---
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值