C++动态规划模板和leetcode原题

1、剑指offer第42题

leetcode 地址连续子数组的最大和 这道题目基本是考察动态规划的最简单题目啦😁

动态规划：

状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])，其中dp[i]表示以索引i为结束点基准的子数组的最大值。

初始状态：dp[0]= nums[0]。

class Solution { public: int maxSubArray(vector<int>& nums) { vector<int> res(0); if(nums.empty()) return 0; res.push_back(nums[0]); for(int i = 1; i < nums.size(); i++) { res.push_back(max(res[i - 1] + nums[i], nums[i])); } return *max_element(res.begin(), res.end()); } };

当然，上面答案其实新开辟了vector<int> res内存空间，如果想继续优化，可以仿照下面思路：

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

或者还有一个思路，循环遍历数组，当累加和大于0时保存累加和，否则重置，代码如下:

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

2. 子数组最大平均数 I（643）

leetcode 地址数组最大平均数 I

这道题几乎和上面那道如出一辙。

先求出前k个数的和sum，然后从k+1个数开始，不断滑窗更新sum。

class Solution { public: double findMaxAverage(vector<int>& nums, int k) { double sum = accumulate(nums.begin(), nums.begin() + k, 0); double res = sum; for (int i = k; i < nums.size(); ++i) { sum += nums[i] - nums[i - k]; res = max(res, sum); } return res / k; } };

剑指 Offer 59 - I. 滑动窗口的最大值

Offer 59 - I. 滑动窗口的最大值这道题和leetcode 239. 滑动窗口最大值一毛一样。

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> res(0); if(nums.empty() || k == 0) { return res; } auto max_iter = max_element(nums.begin(), nums.begin() + k); res.push_back(*max_iter); for(auto iter = nums.begin() + k; iter != nums.end(); iter++) { if(iter - max_iter >= k) { max_iter = max_element(max_iter + 1, iter + 1); } else { if(*iter > *max_iter) max_iter = iter; } res.push_back(*max_iter); } return res; } };