算法刷题--动态规划

动态规划最主要的就是推方程了。
考虑这么一道题目：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

这个就是考虑，当新的元素进来的时候，最大的是加入前缀还是最大的是他自己，
即max( nums[i], nums[i]+dp[i-1] )

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

暴力破解版本，利用那个前缀和的pre[i]-pre[j-1]来解决从j到i之间子数组的和的问题，但超出时间限制。原则上来讲是没问题的。

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