剑指offer 63 股票最大利润：动态规划

剑指 Offer 63. 股票的最大利润

题目描述

假定将某支股票在不同时间点的价格依次存入数组中，试问仅进行一次买卖操作所能获取的最大收益是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第二日（股票价格为 1）时购入，在第五日（股票价格为 6）时售出，所获得的最大收益为 6-1 = 5。需要注意的是，利润不能是 7-1 = 6，因为卖出价格必须高于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情形下，未发生任何交易行为，因此最大收益为 0。

解题思路分析

最初浮现于脑海的思路便是采用暴力求解的方式，即遍历所有可能的数字组合，计算两个数值间的差值，并确保后一数值大于前一数值（即卖出价格高于买入价格）。然而，这种方法所带来的时间复杂度极高。

    public class Solution {
    public int maxProfit(int prices[]) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {