小旭讲解 LeetCode 53. Maximum Subarray 动态规划分治策略

佚名 5年前 (2018-12-26) 算法 1055人围观抢沙发百度已收录

原题

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

讲解

动态规划

视频@ 哔哩哔哩动态规划 or YouTube 动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划的性质

最优子结构（optimal sub-structure）：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
重叠子问题（overlapping sub-problem）：动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

状态转移方程

dp[i] = max(nums[i], nums[i] + dp[i - 1])

解释

i代表数组中的第i个元素的位置
dp[i]代表从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值

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

dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]

时间复杂度

O(n)

参考

动态规划维基百科

代码（C++）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // boundary
        if (nums.size() == 0) return 0;
         
        // delares
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int max = dp[0];
         
        // loop
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = nums[i] > nums[i] + dp[i - 1] ? nums[i] : nums[i] + dp[i - 1];
            if (max < dp[i]) max = dp[i];
        }
         
        return max;
    }
};

分治策略

视频@ 哔哩哔哩分治策略 or YouTube 分治策略

分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。

这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）

实现方式

循环递归

在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
合并：将各子问题的解合并为原问题的解。

注意事项

边界条件，即求解问题的最小规模的判定

示意图

递归关系式

T(n) = 2T(n/2) + n

可以利用递归树的方式求解其时间复杂度（其求解过程在《算法导论》中文第三版 P51有讲解）

时间复杂度

O(nlgn)

代码（C++）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return find(nums, 0, nums.size() - 1);
    }
     
    int find(vector<int>& nums, int start, int end) {
        // boundary
        if (start == end) {
            return nums[start];
        }
        if (start > end) {
            return INT_MIN;
        }
         
        // delcare
        int left_max = 0, right_max = 0, ml = 0, mr = 0;
        int middle = (start + end) / 2;
         
        // find
        left_max = find(nums, start, middle - 1);
        right_max = find(nums, middle + 1, end);
        // middle
        // to left
        for (int i = middle - 1, sum = 0; i >= start; --i) {
            sum += nums[i];
            if (ml < sum) ml = sum;
        }
        // to right
        for (int i = middle + 1, sum = 0; i <= end; ++i) {
            sum += nums[i];
            if (mr < sum) mr = sum;
        }
         
        // return
        return max(max(left_max, right_max), ml + mr + nums[middle]);
    }
};

原题：https://leetcode.com/problems/maximum-subarray

文章来源：胡小旭 => 小旭讲解 LeetCode 53. Maximum Subarray