[贪心算法]买卖股票的最佳时机 买卖股票的最佳时机Ⅱ K次取反后最大化的数组和 按身高排序 优势洗牌（田忌赛马）

1.买卖股票的最佳时机

暴力解法就是两层循环，找出两个差值最大的即可。 优化：在找最小的时候不用每次都循环一遍，只要在i向后走的时候，每次记录一下最小的值即可

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();int ret=0;for(int i=0,prevMin=INT_MAX;i<n;i++)//i是卖的那一天{//1.先更新结果ret=max(ret,prices[i]-prevMin);//2.更新最小值prevMin=min(prices[i],prevMin);}return ret;}
};

2.买卖股票的最佳时机Ⅱ

只需要在每次上升到最高点的时候卖掉即可，这样+起来的总和就是最高利润；

• 当prices[j+1]>prices[j] 时，就让j++
• 走到prices[j+1]<prices[j]就让，i++，j=i 继续向后寻找，直到出现prices[j+1]>prices[j]

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();int ret=0;for(int i=0;i<n;i++){int j=i;while(j+1<n && prices[j+1]>prices[j])j++;ret+=prices[j]-prices[i];i=j;}return ret;}
};

3.K次取反后最大化的数组

我们设m是整个数组中负数的个数，那么就根据m和k的大小进行分类讨论

• m>k （先排序）反转前k个数，再相加
• m==k 把所有的数都当成正数加起来
• m<k

•    1.当k-m是偶数时，就和m==k情况相同
  

•      2.当k-m是奇数时，把绝对值最小的那个数变成负数即可
  

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0;int minElm = INT_MAX;for (int i = 0; i < nums.size(); i++) {if (nums[i] < 0)m++;minElm = min(minElm, abs(nums[i]));}int ret = 0;// 分类讨论if (m > k) {sort(nums.begin(), nums.end());for (int i = 0; i < k; i++) {ret += abs(nums[i]);}for (int i = k; i < nums.size(); i++) {ret += nums[i];}} else if (m == k) {for (int i = 0; i < nums.size(); i++)ret += abs(nums[i]);} else {if ((k - m) % 2 == 0) // 偶数{for (int i = 0; i < nums.size(); i++)ret += abs(nums[i]);}else{for (int i = 0; i < nums.size(); i++)ret += abs(nums[i]);ret=ret-2*minElm;}}return ret;}
};

4.按身高排序

1. 创建一个下标数组
2. 仅需对下标数组排序（根据身高进行排序规则的改变）
3. 根据下标找到对应的字符串

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {//创建一个数组下标int n=heights.size();vector<int> v(n);for(int i=0;i<n;i++)v[i]=i;//重写sort的比较方法sort(v.begin(),v.end(),[&](int i,int j){return heights[i]>heights[j];});//通过下表找到响应的字符串vector<string> ret;for(int i:v){ret.push_back(names[i]);}return ret;}
};

优势洗牌（田忌赛马）

排序（贪心）

1. 最差的能比过就直接比
2. 比不过就去跟对面最大的比，废物利用最大化

步骤：
先对两个数组排序，然后用贪心的思想去排序，这样出来的结果和题目的实例是不一样的；
原因就在于题目的nums2没有排序，所以我们就要用到身高那一题的思想用下标数组来解决，
创建一个index数组，数组的排序规则就是比较nums2中的大小，然后再index数组中创建一个left和right用来记录最大值和最小值

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n=nums2.size();vector<int> ret(n);//存放结果vector<int> index(n);//下标数组for(int i=0;i<n;i++){index[i]=i;}sort(nums1.begin(),nums1.end());//下标数组排序sort(index.begin(),index.end(),[&](int p1,int p2){return nums2[p1]<nums2[p2];});//记录index的左右两边int left=0,right=n-1;for(int i=0;i<n;i++){//贪心：比得过就比，比不过就跟最大的比if(nums1[i]>nums2[index[left]]){ret[index[left++]]=nums1[i];}else{ret[index[right--]]=nums1[i];}}return ret;}
};