1.题目描述

面试题63. 股票的最大利润

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

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

1
0 <= 数组长度 <= 10^5

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package swu.xl.algorithm.code_04_07.experiment_5;

public class Solution {
    /**
     * leetcode 面试题63. 股票的最大利润
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        //除开特殊情况
        if (prices.length == 0 || prices.length == 1){
            return 0;
        }

        //将每天的资金数据转化为当天和前一天的数据差->最大子串和问题
        int[] changes = new int[prices.length-1];
        for (int i = 0; i < changes.length; i++) {
            changes[i] = prices[i+1]-prices[i];
        }

        //存储 最大收益 购买时间 卖出时间的变量
        int maxSum = changes[0];

        //累计收益
        int currentMaxSum = changes[0];

        //遍历每一个位置
        for (int currentIndex = 1; currentIndex < changes.length; currentIndex++){
            //如果累计收益不是正的
            if (currentMaxSum <= 0) {
                //重新计算收益
                currentMaxSum = changes[currentIndex];
            }else {
                //收益累加
                currentMaxSum += changes[currentIndex];
            }

            //如果累计收益大于最大收益
            if (currentMaxSum > maxSum){
                //重新计算最大收益
                maxSum = currentMaxSum;
            }
        }

        //交易没有完成
        if (maxSum < 0){
            maxSum = 0;
        }

        return maxSum;
    }

    /**
     * 测试程序
     * @param args
     */
    public static void main(String[] args) {
        int[] num1 = {7,1,5,3,6,4};

        System.out.println(maxProfit(num1));

        int[] num2 = {7,5,4,3,2,1};

        System.out.println(maxProfit(num2));
    }
}

代码思路：

  • 我们需要计算当前收益，如果收益为负数，就设置为0。

  • 比较当前收益和最大收益，如果当前收益大于最大收益，就将最大收益的值设置为当前收益。

  • 如上图所示，用代码的思路表示出来就可以求解。