股票题目

力扣题目

前几天面试的时候遇到一道题目，假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

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

示例 2:

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

限制：
0 <= 数组长度 <= 10^5

答案

后来思考后，用动态规划写了一下。

public class Solution {
    public int MaxProfit(int[] prices) {
        var minProfit = int.MaxValue;
            var maxProfit = 0;
            foreach (var price in prices)
            {
                minProfit = Math.Min(price,minProfit);
                maxProfit = Math.Max(maxProfit,price-minProfit);
            }
            return maxProfit;
    }
}

总结

在面试这道题目的时候，我一开始就想的是动态规划，但是我遇到一个巨大问题，或者说是一个误区。

比如说，我常常使用动态规划的时候会设想一张表，这其实误区。

我要求得绿色部分的格子，我往往想到的是黄色的部分作为前面的最优解，然后条件改变后的最优解相比。

这里就存在局限性了，表格其实套住了自己的思想，我觉得考虑的点应该是在什么是变化的，变化后会改变什么，从这个点出发就很简单了，表格可以为初级阶段的一个理解。