JZ63 买卖股票的最好时机(一)

描述
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费

炒股就四个字，追涨杀跌，哦，错了，高抛低吸。

解法一：暴力法

使用双层for循环遍历，将每一个元素与后面的每一个元素相比较。

public int maxProfit (int[] prices) {
int max=0;
for(int i=0;i<prices.length-1;i++){
    for(int j=i+1;j<prices.length;j++){
        int temp = prices[j]-prices[i];
        max=temp>max?temp:max;
    }
}
return max;
}
1
2
3
4
5
6
7
8
9
10

复杂度分析：
时间复杂度：O(N[^2])，遍历数组两层
空间复杂度：O(1)，不涉及额外存储空间

解法二：动态规划

每一天都有持有和未持有两种状态，前一天的状态会影响到后一天的状态，可以考虑使用动态规划。

创建一个两列的二维数组，第一列存储未持有，第二列存储持有。

未持有：有两种情况，今天卖出和以前就卖出了，求二者的较大值。今天卖出等于当前价格减去前一天持有价格，以前卖出等于前一天未持有的价格。

持有：有两种情况，今天才买入和以前买入持有到今天，求二者的较小值。今天买入等于当前价格，以前买入等于前一天持有的价格

public int maxProfit (int[] prices) {
  int n =prices.length;
  int[][] dp = new int[n][2];
  dp[0][0]=0;
  dp[0][1]=prices[0];
  for(int i=1;i<n;i++){
      dp[i][0]=Math.max(dp[i-1][0],prices[i]-(dp[i-1][1]));
      dp[i][1]=Math.min(prices[i],dp[i-1][1]);
  }
  return dp[n-1][0];
}
1
2
3
4
5
6
7
8
9
10
11

因为后一天只受前一天的状态影响，所以可以优化去掉二维数组，改用两个中间变量。

动态规划优化：

public int maxProfit (int[] prices) {
   int max=0;
   int temp =0;
   int min=prices[0];
   for(int i=1;i<prices.length;i++){
       max=Math.max(prices[i]-min,max);
       min=Math.min(prices[i],min);
   }
   return max;
}
1
2
3
4
5
6
7
8
9
10

复杂度分析：
时间复杂度：O(N)，遍历数组一次
空间复杂度：O(1)，不涉及额外存储空间

总结：
涉及数据结构：数组
涉及算法：动态规划