力扣题解(动态规划)

53. 最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 求和, >ans 更新 ans, <0 丢弃, >0 保留
        int sum = 0, ans = nums[0];
        for (auto num : nums) {
            sum += num;
            if (sum > ans)
                ans = sum;
            if (sum < 0)
                sum = 0;
        }
        return ans;
    }
};

5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty())
            return "";
        if (s.size() == 1)
            return s;
        string s_tmp = s;
        reverse(s.begin(),s.end());
        string s_rev = s;
        s = s_tmp;
        vector<vector<int> > arr(s.size(), vector<int>(s.size(), 0));
        int end = 0, maxlen = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < s.size(); j++) {
                if (s[i] == s_rev[j]) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxlen) {
                    int before = s.size() - 1 - j;
                    if (before + arr[i][j] - 1 == i) { // 判断下标是否对应
                        maxlen = arr[i][j];
                        end = i;
                    }
                }
            }
        }
        return s.substr(end - maxlen + 1, maxlen);
    }
};

121. 买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划，一趟遍历，记录最小值和最大利润
        int maxProfit = 0;
        int minPrice = INT_MAX;
        for(auto price : prices) {
            if (price < minPrice) {
                minPrice = price;
            }
            if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }
};