Leetcode: Maximum Subarray

忘是亡心i 2022-08-07 09:59 24阅读 0赞

题目：  
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array \[−2,1,−3,4,−1,2,1,−5,4\],  
the contiguous subarray \[4,−1,2,1\] has the largest sum = 6.

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

思路：这道题用一般思路遍历所有结果的话，算法的复杂度是O(n2)。关于这道题网上前辈的做法大多是采用叫动态规划的方法。（个人感觉算法里面所谓的动态规划和传统数学上的动态规划还是有些区别的，关于动态规划的介绍参见：[动态规划][Link 1]）网上有前辈说，动态规划问题最主要是要找出动态规划的递推式。动态规划的解法一般是维护两个变量，局部最优和全局最优，然后利用局部和全局最优变量之间的递推关系进行问题的求解。

为了直观的看清楚问题的求解思路，我们先看一个例子（这个例子摘自《剑指Offer》），下面以表格的形式展现求解的过程（表格也摘自《剑指Offer》）。

![Maximum Subarray][]

可以看到，求解的过程中用到了两个存储变量，一个保存全局的最大的子数组和的globalMax，一个保存局部累加的子数组和的localMax。  
当进行到第i个数据的时候，如果A\[i\]为正数，则localMax+A\[i\]肯定是变大的，大于globalMax，然后将localMax+A\[i\]的结果保存到globalMax中。如果A\[i\]是负数，则localMax+A\[i\]肯定是变小的，小于globalMax，而且localMax+A\[i\]有可能小于A\[i\]（如步骤3）这时我们将localMax的值修改为A\[i\]，即是max(localMax+A\[i\], A\[i\])。  
整理一下思路：  
localMax = max(localMax+A\[i\], A\[i\])  
globalMax= max(globalMax, localMax)  
其实，对于A\[i\]>0的时候，max(localMax+A\[i\], A\[i\])的结果肯定是localMax+A\[i\]，而max(globalMax, localMax)的结果肯定是localMax；当A\[i\]<0的时候，max(localMax+A\[i\], A\[i\])的结果会根据A\[i\]的而有所不同，而max(globalMax, localMax)的结果肯定是globalMax。

C++代码：

class Solution
    {
    public:
        int maxSubArray(int A[], int n)
        {
            if (n <= 0) return 0;
            int globalMax = A[0];
            int localMax = A[0];
            for (int i = 1; i < n; i++)
            {
                localMax = max(localMax + A[i], A[i]);
                globalMax = max(localMax, globalMax);
            }
            return globalMax;
        }
    };

C\#代码：

class Solution { public int MaxSubArray(int[] A) { if (A.Length <= 0) return 0; int globalMax = A[0]; int localMax = A[0]; for (int i = 1; i < A.Length; i++) { localMax = Math.Max(localMax + A[i], A[i]); globalMax = Math.Max(globalMax, localMax); } return globalMax; } }

Python代码：

class Solution:
        # @param A, a list of integers
        # @return an integer
        def maxSubArray(self, A):
            size = len(A)
            if size <= 0:
                return 0
            globalMax = A[0]
            localMax = A[0]
            for i in range(1, size):
                localMax = max(localMax + A[i], A[i])
                globalMax = max(globalMax, localMax)
            return globalMax

先写到这，以后对动态规划有深的理解了，再进行补充！欢迎广大童鞋批评指正，互相学习！

这道题的另一种写法：

class Solution
    {
    public:
        int maxSubArray(int A[], int n)
        {
            if (n <= 0) return 0;
            int globalMax = A[0];
            int localMax = A[0];
            for (int i = 1; i < n; i++)
            {
                if (localMax < 0) localMax = A[i];
                else localMax += A[i];
                if (localMax > globalMax) globalMax = localMax;
            }
            return globalMax;
        }
    };

[Link 1]: http://blog.csdn.net/theonegis/article/details/44751991
[Maximum Subarray]: /images/20220805/2706d077d20246349480b288671cb6e2.png