经典算法-求最大子序列的和

偏执的太偏执、 2022-02-21 10:59 226阅读 0赞

最大连续子序列的和是一道很经典的算法问题，给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（不允许空序列），使它们的和尽可能大。

例：输入序列 \[2,3,-1,4\] , 输出 9

注意：可以假设 输入的数组不为空，同时输入的值都是整数。

**解法一：暴力破解 ，**可以穷举出所有的子序列，然后计算每个子序列的和，时间复杂度是O(N ^ 3)，代码如下：

private static int MaxSum(int[] nums) {
    		if (nums == null || nums.length == 0)
    			return 0;
    
    		int maxSum = nums[0];
    
    		for (int i = 0; i < nums.length; i++) {
    			for (int j = i; j < nums.length; j++) {
    				int sum = 0;
    				for (int k = i; k <= j; k++) {
    					sum += nums[k];
    				}
    				if (sum > maxSum)
    					maxSum = sum;
    			}
    		}
    		return maxSum;
    	}

**解法二：可用用一个数组记录从开始到某个位置的和，例如sum\[i\] 表示从位置0到位置i的和，就可以省略到算法一中的第三层循环，算法的时间复杂度是 O(N ^ 2)**

private static int MaxSum1(int[] nums) {
    		if (nums == null || nums.length == 0)
    			return 0;
    
    		// 存储值
    		int[] sums = new int[nums.length];
    		sums[0] = nums[0];
    		for (int i = 1; i < nums.length; i++) {
    			sums[i] = nums[i] + sums[i - 1];
    		}
    
    		int maxSum = nums[0];
    		for (int i = 0; i < nums.length; i++) {
    			for (int j = i; j < nums.length; j++) {
    				int sum = sums[j] - sums[i];
    				if (sum > maxSum)
    					maxSum = sum;
    			}
    		}
    		return maxSum;
    	}

**解法三 ：分治法，见下图，时间复杂度是** O(N\*logN)

![20190410204334595.png][]

**代码如下：**

private static int maxProduct(int[] nums, int left, int right) {
    		// 序列长度为1时
    		if (left == right) {
    			return nums[left];
    		}
    
    		// 划分为两个规模更小的子问题
    		int mid = (left + right) >> 1;
    		int iMaxLeft = maxProduct(nums, left, mid);
    		int iMaxRight = maxProduct(nums, mid + 1, right);
    
    		// 横跨分割点的情况
    		int sum = 0, lmax = nums[mid], rmax = nums[mid + 1];
    		for (int i = mid; i >= left; i--) {
    			sum += nums[i];
    			if (sum > lmax)
    				lmax = sum;
    		}
    
    		sum = 0;
    		for (int i = mid + 1; i <= right; i++) {
    			sum += nums[i];
    			if (sum > rmax)
    				rmax = sum;
    		}
    
    		// 答案是三种情况的最大值
    		int ans = lmax + rmax;
    		if (iMaxLeft > ans)
    			ans = iMaxLeft;
    		if (iMaxRight > ans)
    			ans = iMaxRight;
    
    		return ans;
    	}

**解法四：动态规划**

设置 dp\[i\] 表示以第i个数结尾的最大子序列的和，则 可以推导出以下公式

**dp\[n\] = max(0, dp\[n-1\]) + nums\[n\]。**则最大子序列的和是 `max(dp[m]) | m∈[0, N-1]`。

**代码如下：**

private static int MaxSum3(int[] nums) {
    		if (nums == null || nums.length == 0)
    			return 0;
    
    		int maxSum = nums[0];
    		for (int i = 1; i < nums.length; i++) {
    
    			// 计算max(0,dp[i-1]) 的值，此处可以单独创建一个dp数组，但是根据递推关系，可以直接使用原数组存储
    			nums[i] += Math.max(0, nums[i - 1]);
    
    			// 获取max(dp[m])
    			if (nums[i] > maxSum)
    				maxSum = nums[i];
    		}
    		return maxSum;
    	}

[20190410204334595.png]: /images/20220221/01c5d8e410c6437e9b784413faeedb39.png