1. One buy one sell for max profit

Say you have an array for which the i element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0

Peak Valley Approach

Algorithm
Say the given array is:
[7, 1, 5, 3, 6, 4].
If we plot the numbers of the given array on a graph, we get:
贪心算法（最优选择） - 图1
The key point is we need to consider every peak immediately following a valley to maximize the profit. In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over one of the transactions leading to an overall lesser profit.
For example, in the above case, if we skip peaki_peak__i and valleyj_valley__j trying to obtain more profit by considering points with more difference in heights, the net profit obtained will always be lesser than the one obtained by including them, since C will always be lesser than A+B

时间复杂度O（n）
**

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int i = 0;
  4.         int valley = prices[0];
  5.         int peak = prices[0];
  6.         int maxprofit = 0;
  7.         while (i < prices.length - 1) {
  8.             while (i < prices.length - 1 && prices[i] >= prices[i + 1])
  9.                 i++;
  10.             valley = prices[i];
  11.             while (i < prices.length - 1 && prices[i] <= prices[i + 1])
  12.                 i++;
  13.             peak = prices[i];
  14.             maxprofit += peak - valley;
  15.          return maxprofit;
  16.         }

改进

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int maxprofit = 0;
  4.         for (int i = 1; i < prices.length; i++) {
  5.             if (prices[i] > prices[i - 1])
  6.                 maxprofit += prices[i] - prices[i - 1];
  7.         }
  8.         return maxprofit;
  9.     }
  10. }

2. 二维数组——画家小Q

画家小Q又开始他的艺术创作。小Q拿出了一块有NxM像素格的画板, 画板初始状态是空白的,用’X’表示。
小Q有他独特的绘画技巧,每次小Q会选择一条斜线, 如果斜线的方向形如’/‘,即斜率为1,小Q会选择这条斜线中的一段格子,都涂画为蓝色,用’B’表示;如果对角线的方向形如’\’,即斜率为-1,小Q会选择这条斜线中的一段格子,都涂画为黄色,用’Y’表示。
如果一个格子既被蓝色涂画过又被黄色涂画过,那么这个格子就会变成绿色,用’G’表示。
小Q已经有想画出的作品的样子, 请你帮他计算一下他最少需要多少次操作完成这幅画。

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数N和M(1 <= N, M <= 50), 表示画板的长宽。
接下来的N行包含N个长度为M的字符串, 其中包含字符’B’,’Y’,’G’,’X’,分别表示蓝色,黄色,绿色,空白。整个表示小Q要完成的作品。

输出描述:

输出一个正整数, 表示小Q最少需要多少次操作完成绘画。
示例1
输入
4 4
YXXB
XYGX
XBYY
BXXY
输出
3
说明
XXXX
XXXX
XXXX
XXXX
->
YXXX
XYXX
XXYX
XXXY
->
YXXB
XYBX
XBYX
BXXY
->
YXXB
XYGX
XBYY
BXXY

算法：首先读懂题意，其中 ‘/‘必须涂蓝色 ‘\’必须涂黄色
基本思想：将所给二维数组还原成原来空白情况，即全部为’X’，为此只需遍历（并修改）数组的所有字符。对于每一个字符，如果是’B’就向左下扫描，遇到’B’或者’G’则继续（在左下扫描过程中，将所有的B替换为X，G替换成Y），否则立即停止；如果字符是’Y’，就向右下扫描，遇到Y或者G继续（将所有的Y替换成X，G替换成B），否则停止扫描；如果字符是G，则先将其替换成B，按’B’处理方式扫描，再将其替换成Y，按Y的处理方式扫描。每执行一次左下或者右下扫描，操作次数+1。

  1. 链接：https://www.nowcoder.com/questionTerminal/6acc6504df67406c98a75f5575e4b94a
  2. 来源：牛客网
  4. #include <iostream>
  5. #include <vector>
  6. using namespace std;
  8. void refix(vector<vector<char>>& arr,int& n,int& m,int x,int y,int& ans){//B Y
  9.     char ch = arr[x][y];
  10.     arr[x][y]='X';
  11.     int i,j;
  13.     if(ch=='B'){//左下画线
  14.         i=x+1;j=y-1;
  15.         while(i<n && j>-1){
  16.             if(arr[i][j]==ch) arr[i][j]='X';
  17.             else if(arr[i][j]=='G') arr[i][j]='Y';
  18.             else break;
  19.             ++i,--j;
  20.         }
  21.     }
  22.     else{//右下画线
  23.         i=x+1;j=y+1;
  24.         while(i<n && j<m){
  25.             if(arr[i][j]==ch) arr[i][j]='X';
  26.             else if(arr[i][j]=='G') arr[i][j]='B';
  27.             else break;
  28.             ++i,++j;
  29.         }
  30.     }
  32.     ans+=1;
  33. }
  35. int main(){
  36.     int N,M;
  37.     cin >> N >> M;
  38.     vector<vector<char>> arr(N,vector<char>(M));
  39.     for(int i=0;i<N;++i){
  40.         for(int j=0;j<M;++j)
  41.             cin >> arr[i][j];
  42.     }
  43.     int ans = 0;
  44.     for(int i=0;i<N;++i){
  45.         for(int j=0;j<M;++j){
  46.             if(arr[i][j]=='X') continue;
  47.             else if(arr[i][j]=='B') refix(arr,N,M,i,j,ans);
  48.             else if(arr[i][j]=='Y') refix(arr,N,M,i,j,ans);
  49.             else {//当前为'G'
  50.                 arr[i][j]='B';refix(arr,N,M,i,j,ans);
  51.                 arr[i][j]='Y';refix(arr,N,M,i,j,ans);
  52.             }
  53.         }
  54.     }
  55.     cout << ans;
  56.     return 0;
  58. }