1.打家劫舍
题目:打家劫舍
滚动变量节省空间;
因为不能连续取值,递推公式:当前最大值=max(上一个,上上一个 + 当前值)
class Solution {
public:
int rob(vector<int>& nums) {
int f0 = 0, f1 = 0;
for (int x : nums) {
int new_f = max(f1, f0 + x);
f0 = f1;
f1 = new_f;
}
return f1;
}
};
2.最大子数组和
题目:最大子数组和
求一个数组中,和最大的子数组。一种是前缀和:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
int min_pre_sum = 0;
int pre_sum = 0;
for (int x : nums) {
pre_sum += x; // 当前的前缀和
ans = max(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
min_pre_sum = min(min_pre_sum, pre_sum); // 维护前缀和的最小值
}
return ans;
}
};
一种是动规:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN; // 注意答案可以是负数,不能初始化成 0
int f = 0;
for (int x : nums) {
f = max(f, 0) + x;
ans = max(ans, f);
}
return ans;
}
};
标签:pre,f1,nums,int,sum,ans,动态,规划
From: https://www.cnblogs.com/Amroning/p/18528868