算法-股票交易

版权声明： https://blog.csdn.net/li_xunhuan/article/details/89789441

题目： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

代码：
	public class Solution {
public int maxProfit(int prices[]) {
    int minprice = Integer.MAX_VALUE;
    int maxprofit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minprice)
            minprice = prices[i];
        else if (prices[i] - minprice > maxprofit)
            maxprofit = prices[i] - minprice;
    }
    return maxprofit;
}
}

分析： 这件事情的理论是这样的： 从开始找一个最小的，于是在向后查询表，后面找一个最大的波峰； 但是有可能找到更小的，于是波谷更新了；但是，注意要点是前一个波谷和其后面最高波峰之间的差值没有因更小的波谷出现而更新，而是直到二号波谷和其后的波峰差值最大值比上一个差值还大才去覆盖它； 此处有一个理论，如果由于波谷的更新，二号波谷后面的波峰与一号波谷的差额只会比二号波谷和其后面的波峰差值小。

在这里插入图片描述