本篇文章，我将同大家一起学习c++的贪心！！！
目录
第一题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i = 1; i < n; i++)
{
if(ret.back() < nums[i]) ret.push_back(nums[i]);
else
{
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) >> 1;
if(ret[mid] < nums[i]) left = mid + 1;
else right = mid;
}
ret[left] = nums[i];
}
}
return ret.size();
}
};
第二题
题目链接
题目解析
解释：三元子序列:条件：1.i - 1 < i < i + 1 2.nums[i - 1] < nums[i] < nums[i + 1]
代码原理
代码编写
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
int a = nums[0], b = INT_MAX;
for(int i = 1; i < n; i++)
{
if(nums[i] > b) return true;
else if( nums[i] > a) b = nums[i];
else a = nums[i];
}
return false;
}
};
第三题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size(), ret = 0;
for(int i = 0; i < n;)
{
int j = i + 1;
while(j < n && nums[j] > nums[j - 1]) j++;
ret = max(ret, j - i);
i = j;
}
return ret;
}
};
第四题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), ret = 0;
int min_prices = INT_MAX, max_prices = 0;
for(int i = 0; i < n; i++)
{
min_prices = min(min_prices, prices[i]);
max_prices = max(max_prices, prices[i] - min_prices);
}
return max_prices;
}
};
第五题
题目链接
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ret = 0;
for(int i = 0; i < prices.size(); i++)
{
if(i + 1 < prices.size() && prices[i] < prices[i + 1]) ret += prices[i + 1] - prices[i];
}
return ret;
}
};
思路拓展
第一种思路：找到上升段，然后末减初
第二种思路：找到每一上升小段，就进行一次末减初，然后移动右指针，持续计算，求出最大结果
代码
int n = prices.size();
int ret = 0;
// for(int left = 0; left < n; left++)
// {
// int right = left;
// while(right + 1 < n && prices[right + 1] > prices[right])
// {
// right++;
// }
// ret += prices[right] - prices[left];
// left = right;
// }第六题
题目链接
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int n = nums.size(), m = 0, min_nums = INT_MAX,ret = 0;
for(int i = 0; i < n; i++)
{
if(nums[i] < 0)
m++;
min_nums = min(min_nums, abs(nums[i]));
}
if(m > k)
{
sort(nums.begin(),nums.end());
for(int i = 0; i < k; i++)
{
ret += -nums[i];
}
for(int i = k; i < n; i++)
{
ret += nums[i];
}
}
else
{
for(auto cur: nums)
{
ret += abs(cur);
}
if((k - m) % 2)
ret -= min_nums * 2;
}
return ret;
}
};
注意：这里的最小值一定要记得加绝对值。
本篇文章的内容就先到这里，最后也祝大家除夕快乐，春节快乐！！！
记得一键三连哦！！！
