leetcode 53. Maximum Subarray 动态规划DP + 最大子串和

青旅半醒 2022-06-09 10:28 195阅读 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.

这道题就是经典的最大子串和的问题，使用循环或者优化过后的循环肯定会超时，这个题最好采用DP，主要参考这个链接：[DP动态规划——最大数字子串][DP]

**注意要考虑到全是负数的情况，分情况讨论即可**

设计一个输入数组a\[i\],用数组dp\[i\]记录最后一个数为a\[i\]时的最大子串和，状态转移方程为 :  
**dp\[i\] = max(dp\[i-1\]+a\[i\],a\[i\]);**  
初始条件dp\[0\]=a\[0\]， 然后dp\[i\]中最大元素即为所求。

当然也可以使用一个变量来表示最大值，而不是建立一个dp数组，这个参见第二个解决方法。

代码如下：

public class Solution
    {
        
        /*
         * 输入数组a[i],用数组dp[i]记录最后一个数为a[i]时的最大子串和
         * 状态转移方程为 : dp[i] = max(dp[i-1]+a[i],a[i]); 1<=i<n-1  
         * 初始条件dp[0]=a[0]
         * 然后dp[i]中最大元素即为所求。 
         * */
        public int maxSubArray(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            int []dp=new int[nums.length];
            dp[0]=nums[0];
            for(int i=1;i<nums.length;i++)
            {
                dp[i]=Math.max(dp[i-1]+nums[i], nums[i]);
    /*          if(dp[i-1]<0)
                    dp[i]=nums[i];
                else 
                    dp[i]=dp[i-1]+nums[i];*/
            }
    
            int maxSum=dp[0];
            for(int i=0;i<dp.length;i++)
                maxSum=Math.max(maxSum, dp[i]);
    
            return maxSum;
        }
    
        public int maxSubArrayWithO1(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            //最大子串问题
            int len=nums.length;
            int sum=Integer.MIN_VALUE;
    
            //DP解决  ，一定要记着
            int dp=0;
            for(int i=0;i<len;i++)
            {
                if(dp>0)
                    dp+=nums[i];
                else 
                    dp=nums[i];
                sum=Math.max(sum, dp);
            }
    
            return sum;
        }
    
        /*
         * 通过最直接的循环来做
         * 
         * */
        public int maxSubArrayByLoop(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            //最大子串问题
            int len=nums.length;
            int sum=Integer.MIN_VALUE;
    
            /*//循环解决，肯定会超时
            for(int i=0;i<len;i++)
            {
                for(int j=i;j<len;j++)
                {
                    int tt=0;
                    for(int k=i;k<=j;k++)
                    {
                        tt+=nums[k];
                    }
                    sum=(tt >= sum)? tt : sum;
                }
            }*/
    
            //优化方案，但是也极有可能超时
            for(int i=0;i<len;i++)
            {
                int tt=0;
                for(int j=i;j<len;j++)
                {
                    tt+=nums[j];
                    sum=(tt >= sum)? tt : sum;
                }
            }
    
            return sum;
        }
    }

下面是C++的动态规划做法，很简单，也很经典，必须要记住

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int maxSubArray(vector<int>& a)
        {
            if (a.size() <= 0)
                return 0;
            int res = INT_MIN, dp = 0;
            for (int i = 0; i < a.size(); i++)
            {
                if (dp > 0)
                    dp += a[i];
                else
                    dp = a[i];
                res = max(res, dp);
            }
            return res;
        }
    
        int maxSubArrayByDP(vector<int>& a) 
        {
            if (a.size() <= 0)
                return 0;
            vector<int> dp(a.size(), 0);
            dp[0] = a[0];
            for (int i = 1; i < a.size(); i++)
                dp[i] = max(dp[i - 1] + a[i], a[i]);
            return *max_element(dp.begin(), dp.end());
        }
    };

**注意要考虑到全是负数的情况，分情况讨论即可**，不过本题没有这个问题

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    #include <array>
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int maxSubArray(vector<int>& a) 
        {
            bool flag = false;
            for (int i=0;i<a.size();i++)
            {
                if (a[i] >= 0)
                    flag = true;
            }
    
            if (flag == true)
            {
                int sum = 0;
                int dp = 0;
                for (int i = 0; i<a.size(); i++)
                {
                    if (dp > 0)
                        dp += a[i];
                    else
                        dp = a[i];
    
                    sum = max(sum, dp);
                }
                return sum;
            }
            else
                return *max_element(a.begin(), a.end());
        }
    };

[DP]: http://blog.csdn.net/someday7_toi/article/details/7852448