乐趣区

关于算法-数据结构:Leetcode-121-买卖股票的最佳时机

给定一个数组 prices,它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。

你只能抉择 某一天 买入这只股票,并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0

示例 1:

输出: [7,1,5,3,6,4]
输入: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5。
留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

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

暴力法

写两层 for 循环,一一比拟,必定能比进去,代码就不写了。

工夫复杂度:O(n2)
空间复杂度: O(1)

动静布局

定义子问题

假如咱们曾经晓得 i-1 个股票的最大利润为 dp[i-1],显然 i 个间断股票的最大利润要么是 dp[i-1],要么就是 prices[i] - minpriceminprice 为前 i-1 支股票的最小值)。

状态转移方程

dp[i] = Math.max(dp[i-1], prices[i] - minprice)

边界条件

dp[0] = 0

代码实现

因为咱们在计算 dp[i] 的时候,只关怀 dp[i-1]prices[i],因而不必把整个 dp 数组保留下来,只需设置一个 max 保留 dp[i-1] 就好了。

public class Solution {public int maxProfit(int[] prices) {
        int max = 0;
        int minprice = prices[0];
        for (int i=1; i<prices.length; i++) {minprice = Math.min(prices[i], minprice);
            max = Math.max(max, prices[i] - minprice);
        }
        return max;
    }
}

工夫复杂度:O(n)
空间复杂度:O(1)

退出移动版