《算法设计与分析》第四章：贪心算法

5.股票买卖

• 第一问：从前往后遍历双指针，每次后指针比前指针所指元素小，则前指针赋值为后指针，反之，则计算此时的收益和ans做比较

#include 

using namespace std;

const int MMM = 10010;
int a[MMM];
int n, ans;

void solve()
{
	int i = 1, j = 2;
	for(; j <= n; j ++ )
	{
		if(a[i] > a[j])
		{
			i = j;
		}
		else
		{
			ans = max(ans, a[j] - a[i]);
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
	}
	solve();
	cout << ans << endl;
	
	return 0;
}

• 第二问：找上涨区间即可

#include 

using namespace std;

const int MMM = 10010;
int a[MMM];
int n, ans;

void solve()
{
	int i = 1, j = 1;
	for(; j <= n; j ++ )
	{
		if(a[j+1] < a[j])
		{
			ans = ans + a[j] - a[i];
			i = j + 1;
		}
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
	}
	solve();
	cout << ans << endl;
	
	return 0;
}

• 进阶：如果手续费需要2

#include 
#include 

using namespace std;

int maxProfit(vector& prices, int fee) 
{
	int n = prices.size();
	int profit = 0;
	int buyPrice = prices[0];  // 初始买入价格设为第一天的价格
	
	for (int i = 1; i < n; ++i) {
		// 如果当前价格低于之前的买入价格，则考虑在这一天买入
		if (prices[i] < buyPrice) 
		{
			buyPrice = prices[i];
		}
		
		// 如果当前价格减去买入价格大于交易费用，则考虑卖出
		if (prices[i] > buyPrice + fee) 
		{
			profit += prices[i] - buyPrice - fee;  // 计算这次交易的利润
			buyPrice = prices[i] - fee;  // 更新买入价格为当前价格减去交易费用
			// 这一步是为了防止在价格小幅波动时重复交易
		}
	}
	
	return profit;
}

int main() 
{
	vector prices = {1, 3, 2, 8, 4, 9};
	int fee = 2;
	cout << "最大利润: " << maxProfit(prices, fee) << endl;
	return 0;
}

6.摇摆序列

一个整数序列，如果两个相邻元素的差恰好正负（或负正）交替出现，则该序列称为摇摆序列，一个小于2个元素的序列直接为摇摆序列 。给一个随机序列，求这个序列的最长摇摆子序列长度。

• 算有几个转折点即可

#include

using namespace std;

int n;

int wig(vector &nums)
{
	if(nums.size() < 2) return nums.size();
	
	static const int BEGIN = 0;
	static const int UP = 1;
	static const int DOWN = 2; //扫描时候的三种状态
	
	int STATE = BEGIN;
	int max_length = 1;//摇摆序列最大长度至少为1,0个和1个元素就返回了，现在至少两个元素 
	
	for(int i = 1 ; i < nums.size() ; i++)
	{
		switch(STATE){ //当前状态-起始状态 
		case BEGIN:
			if(nums[i-1] < nums[i]){ //上升时候 
				STATE = UP; //状态转移 
				max_length++; 
			}else if(nums[i-1] > nums[i]){ //下降时候 
				STATE = DOWN;
				max_length++;
			}
			break; 
			
		case UP:
			if(nums[i-1] > nums[i]){
				STATE = DOWN;
				max_length++;
			}
			break;
			
		case DOWN:
			if(nums[i-1] < nums[i]){
				STATE = UP;
				max_length++;
			}
			break;
		} //switch 
	} //for 
	return max_length;	
} 

int main()
{
	vector v;
	cin >> n;
	while(n--)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}
	cout<