[剑指Offer]-股票的最大利润

题目描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？

例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.

解题思路

• 暴力比较：时间复杂度O（n^2）
• 最大利润无外乎就是计算后面的数字减去前面的数字得到的一个最大的差值，当我们确定卖出价后，只需要找到一个最小的买入价即可
• 最小买入价格，当前利润，最大利润。时间复杂度O(n)

算法图解

参考代码：

package offer;

/**
 * 股票的最大利润
 * 例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.
 */
public class Offer63 {
    public static void main(String[] args) {
        int nums[] = {9, 11, 8, 5, 7, 12, 16, 14};
        System.out.println(maxDiff(nums));
    }

    static int maxDiff(int nums[]) {
        if (nums == null) {
            return 0;
        }
        // 最小买入
        int minbugIn = nums[0];
        //最大利润
        int maxDiff = nums[1] - minbugIn;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i-1] < minbugIn) {
                minbugIn = nums[i];
            }
            int currentDiff=nums[i]-minbugIn;
            if(currentDiff>maxDiff){
                maxDiff=currentDiff;
            }
        }
        return maxDiff;
    }

}

附录

该题源码在我的 ????Github 上面！