一、Leetcode——最大子序和

最大子数组和
本题有3种写法：暴力法、贪心法、动态规划法

1. 暴力法

• 暴力法使用双层for循环，寻找最大的result,最后return result
• 超时

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result=INT_MIN;
        for(int i=0;i<nums.size();i++){
            int count=0;
            for(int j=i;j<nums.size();j++){
                count+=nums[j];
                result=count>result?count:result;
            }
        }
        return result;
    }
};

2.贪心法

• 贪心法要寻找局部最优解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result=INT_MIN;
        int count=0;
        for(int i=0;i<nums.size();i++){
            count+=nums[i];
            if(count>result){
                result=count;
            }
            if(count<=0){
                count=0;//这一步很牛
            }
        }
        return result;
    }
};

3.动态规划法

• 声明一个vector dp，长度为nums.size()
• 递推公式dp[i]=max(dp[i-1]+nums[i],nums[i])
• result=dp[i]最大值，最后return dp[i]

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