分治算法

港控/mmm° 2022-12-12 04:58 307阅读 0赞

划分问题：整个问题划分成多个无关联的子问题。  
递归求解：递归调用求解各个子问题。  
合并问题：合并子问题的解，形成原始问题的解。

--------------------

以[Leetcode][]数组的连续数列最大和例子为例：

> 输入： \[-2,1,-3,4,-1,2,1,-5,4\]  
> 输出： 6  
> 解释： 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

--------------------

# 分治实现： #

分治思路：

> nums = \[-2,1,-3,4,-1,2,1,-5,4\]

首先，将问题划分为多个无关的子问题，在这里将整个数组每次递归划分为两部分nums1和nums2，那么最大连续子序列和只有3种情况：

> nums1 = \[-2,1,-3,4,-1\]  
> nums2 = \[2,1,-5,4\]

1、最大连续和子序列在nums1
    2、最大连续和子序列在nums2
    3、由nums1的后部分和nums2的前部分组成

--------------------

# 实现代码： #

class Solution {
        
    public:
        
        int devide(vector<int>& nums, int left, int right) {
        
            if (left == right) {
        
                return nums[left];
            }
            int mid = (left + right) / 2;
            int leftSum = devide(nums, left, mid); // 左边最大和
            int rightSum = devide(nums, mid + 1, right); // 右边最大和
            int sumLeft = 0, maxLeftSum = INT_MIN;
            for (int i = mid; i >= left; --i) {
        
                sumLeft += nums[i];
                maxLeftSum = max(maxLeftSum, sumLeft); 
            }
            int sumRight = 0, maxRightSum = INT_MIN;
            for (int i = mid + 1; i <= right; ++i) {
        
                sumRight += nums[i];
                maxRightSum = max(maxRightSum, sumRight);
            }
            return max(max(leftSum, rightSum), maxRightSum + maxLeftSum);
            // 情况3是maxRightSum + maxLeftSum的和
        }
        int maxSubArray(vector<int>& nums) {
        
            int left = 0;
            int right = nums.size() - 1;
            return devide(nums, left, right);
        }
    };

[Leetcode]: https://leetcode-cn.com/problems/contiguous-sequence-lcci/