【算法导论笔记】最大连续子序列和

柔光的暖阳◎ 2022-05-08 13:04 149阅读 0赞

分别采用两种方法实现：

1.  分而治之递归解法
2.  线性数学解法

### 1. 分而治之递归解法 ###

分为三种情况，

1.  最大子序列和完全在左子数组；
2.  最大子序列和完全在右子数组；
3.  跨越了中间；

#### 关键代码 ####

/* 通过初始化值，完美规避，必须包含 mid 的子序列 */
    int findMaxCrossingSubArray(int * A, int low, int mid, int high)
    {
    	int leftIndex = mid;
    	int rightIndex = mid;
    	int leftSum = 0;
    	int rightSum = 0;
    	int leftFinalSum = A[mid];
    	int rightFinalSum = 0;
    
    
    	for (int i = mid; i >= 0; i--)
    	{
    		leftSum += A[i];
    		if (leftSum > leftFinalSum)
    		{
    			leftIndex = i;
    			leftFinalSum = leftSum;
    		}
    	}
    
    	for (int i = mid + 1; i < high; i++)
    	{
    		rightSum += A[i];
    		if (rightSum > rightFinalSum)
    		{
    			rightIndex = i;
    			rightFinalSum = rightSum;
    		}
    	}
    
    	return leftFinalSum + rightFinalSum;
    }
    
    int findMaximumSubarray(int *A, int low, int high)
    {
    	if (low == high)
    	{
    		return A[low];
    	}
    	// 注意 mid 的计算方法
    	int mid = (high + low) / 2;
    	int left = findMaximumSubarray(A, low, mid);
    	int right = findMaximumSubarray(A, mid + 1, high);
    	int cross = findMaxCrossingSubArray(A, low, mid, high);
    	
    	return max(max(left, right), cross);
    }

### 2. 数学思路 ###

如果前面加和为负数，我就选择不加，如果是正数我就加入，最终每次加入都需要和之前的结果比较取一个大值返回！参考 int findMaximumSubarray2(int \*A, int size);

#### 关键代码 ####

int findMaximumSubarray2(int *A, int size)
    {
    	int sum = 0;
    	int result = A[0];
    	for (int i = 0; i < size; i++)
    	{
    		if (sum < 0)
    		{
    			sum = 0;
    		}
    
    		sum += A[i];
    		result = result > sum ? result : sum;
    	}
    	return result;
    }

### 3. 总结 ###

方法 2 的时间复杂度较低，方法 2 更多的是人为的做了分析取舍，精进了算法，导致问题变得简单。  
学而不思则罔，学会了计算机的技能之后，再加上数学的思维，往往会事半功倍！

#### 完整的测试验证代码： ####

#include "pch.h"
    #include <iostream>
    
    #define max(a, b) a > b ? a : b
    
    int findMaxCrossingSubArray(int * A, int low, int mid, int high);
    int findMaximumSubarray(int *A, int low, int high);
    int findMaximumSubarray2(int *A, int size);
    
    int main()
    {
    	int a[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
    	std::cout << findMaximumSubarray(a, 0, 15) << std::endl;
    	std::cout << findMaximumSubarray2(a, sizeof(a) / sizeof(a[0])) << std::endl;
    	return 0;
    }
    
    /* 通过初始化值，完美规避，必须包含 mid 的子序列 */
    int findMaxCrossingSubArray(int * A, int low, int mid, int high)
    {
    	int leftIndex = mid;
    	int rightIndex = mid;
    	int leftSum = 0;
    	int rightSum = 0;
    	int leftFinalSum = A[mid];
    	int rightFinalSum = 0;
    
    
    	for (int i = mid; i >= 0; i--)
    	{
    		leftSum += A[i];
    		if (leftSum > leftFinalSum)
    		{
    			leftIndex = i;
    			leftFinalSum = leftSum;
    		}
    	}
    
    	for (int i = mid + 1; i < high; i++)
    	{
    		rightSum += A[i];
    		if (rightSum > rightFinalSum)
    		{
    			rightIndex = i;
    			rightFinalSum = rightSum;
    		}
    	}
    
    	return leftFinalSum + rightFinalSum;
    }
    
    int findMaximumSubarray(int *A, int low, int high)
    {
    	if (low == high)
    	{
    		return A[low];
    	}
    	// 注意 mid 的计算方法
    	int mid = (high + low) / 2;
    	int left = findMaximumSubarray(A, low, mid);
    	int right = findMaximumSubarray(A, mid + 1, high);
    	int cross = findMaxCrossingSubArray(A, low, mid, high);
    	
    	return max(max(left, right), cross);
    }
    
    int findMaximumSubarray2(int *A, int size)
    {
    	int sum = 0;
    	int result = A[0];
    	for (int i = 0; i < size; i++)
    	{
    		if (sum < 0)
    		{
    			sum = 0;
    		}
    
    		sum += A[i];
    		result = result > sum ? result : sum;
    	}
    	return result;
    }