题意整理

• 已知股票每一天的价格波动。
• 最多持有一只股，也就是买入时必须卖出之前持有的股。
• 只能买入和卖出股票一次，求最大收益。

方法一（暴力）

1.解题思路

只需两层循环，第一层遍历所有元素，第二层遍历当前元素之后所有元素，记录后者与前者之间差值的最大值，取最大的差值即是最大收益。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;
        //记录最终收益
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                //取所有间隔中差值最大的作为收益
                res=Math.max(res,prices[j]-prices[i]);
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：需要两层循环，总共执行$n\ast (n-1)\mathrm{/}2n*(n-1)/2$次操作，所以时间复杂度为$O(n^2)O(n^2)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。

方法二（动态规划）

1.解题思路

遍历每一天的价格，用一个变量记录收益的变化，要么取当前收益，要么用当前价格减去最小价格作为收益，取两者中的较大值。遍历完成之后，所得的收益即是最大的收益。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int n=prices.length;
        //记录最小价格
        int min=prices[0];
        //记录最终收益
        int res=0;
        for(int i=1;i<n;i++){
            //要么取当前收益，要么用当前价格减去最小价格作为收益
            res=Math.max(res,prices[i]-min);
            min=Math.min(min,prices[i]);            
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：只需一层循环，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$ 。