题解 | #买卖股票的最好时机(二)#

思路：

• 思路1，动归，最优解具有最优子问题和重叠子问题的特点，发现状态有当前持有股票和不持有股票两种，所以两种都要考虑，用f[i][0]代表第i天未持有股票的最大收益，f[i][1]代表第i天持有股票的收益，然后推导当前和前一天的关系，注意，最后一定是不能持有股票的，因为这样相当于买这支股票没有收益，只有支出，所以对收益的贡献必为负，所以只需返回最后一天不持有股票的结果

• 思路2，只要股票涨价，就卖出，所有涨价的收益集合就是最大的收益

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        //思路2，只要股票涨价，就卖出，所有涨价的收益集合就是最大的收益
        if(prices.length == 1){
            return 0;
        }
        int profit = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] >  prices[i-1] && i >=1  ) {
                profit = profit + prices[i] - prices[i-1];
            }
        }
        return profit;
        
//         //动归的空间优化
//         int n=prices.length;
//         int a=0,b=-prices[0];
//         for(int i=1;i<=n;i++){
//             int c=a;
//             a=Math.max(a,b+prices[i-1]);
//             b=Math.max(b,c-prices[i-1]);
//         }
//         return a;
        
//         //动归，最优解具有最优子问题和重叠子问题的特点，发现状态有当前持有股票和不持有股票两种，所以两种都要考虑，用f[i][0]
//         //代表第i天未持有股票的最大收益，f[i][1]代表第i天持有股票的收益，然后推导当前和前一天的关系，注意，最后一定是不能持有股票的，因为这样相当于买这支股票没有收益，只有支出，所以对收益的贡献必为负，所以只需返回最后一天不持有股票的结果
//         int n=prices.length;
//         int[][] profits=new int[n+1][2];
//         profits[0][1]=-prices[0];
//         for(int i=1;i<=n;i++){
//             profits[i][0]=Math.max(profits[i-1][0],profits[i-1][1]+prices[i-1]);
//             profits[i][1]=Math.max(profits[i-1][1],profits[i-1][0]-prices[i-1]);
//         }
//         return profits[n][0];
    }
}