贪心的本质：局部最优推出全局最优
53. 最大子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
//贪心算法
//从第一个开始计算序列和，一旦和变为负数，那么就重置为0，重新计算后面序列的和
int maxSubArray(vector<int>& nums) {
int count = 0;//储存每段序列的和
int ret = INT_MIN;//储存最大返回的结果
for(int i = 0; i < nums.size(); i++)
{
count += nums[i];//每次都加上和
if(count > ret) ret = count;//判断此时是否要更新最大值
if(count <= 0) count = 0;//如果此时序列和已经小于0了，那么重置count
}
return ret;
}
};
注意ret要初始化为int的最小值，如果输入的全是负数，那么取最大的负数作为答案，
122. 买卖股票的最佳时机 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
//没买状态下，当 明天比今天高，买今天
//买的状态下，当 明天比今天低，卖今天
int maxProfit(vector<int>& prices) {
bool isPurchased = false;//状态机
int in;//买入价格
int result = 0;//利润
for(int i = 0; i < prices.size() - 1; i++)
{
if(!isPurchased)
{
if(prices[i + 1] > prices[i])
{
in = prices[i];
isPurchased = true;//进入买的状态
}
}
else
{
if(prices[i + 1] < prices[i])
{
result += (prices[i] - in);
isPurchased = false;//返回没买的状态
}
}
}
//如果到最后一天了手上的股票还没卖，说明一直涨到最后一天了
if(isPurchased) result += prices[prices.size() - 1] - in;
return result;
}
};
这是我的思路，我的想法就是判断明天价格和今天的关系来决定是否买卖。
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
这是代码随想录的方案。这个意思就是把利润分解为每天的利润，使用贪心把正利润求和就是最终结果，负利润不管。
假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。