买卖股票的最佳时机

2021-02-05

买卖股票的最佳时机

题目描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

示例
示例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解决方法：贪心算法

贪心算法：求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法(greedy algorithm)就是这样的算法。它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。

解题思路
股票买卖策略：

单独交易日：设今天价格p1、明天价格p2,则今天买入，明天卖出可赚取p2 - p1(负值代表亏损)
连续上涨交易日：设此上涨交易日股票价格分别为p1, p2, … pn,则第一天买入，最后一天卖出收益最大，即pn -p1,等价于每天都买卖，即pn - p1 = (p2 - p1) + (p3 - p2) + (p4 - p3) + … + (pn - pn-1)
连续下降交易日: 则不买卖收益最大，即不会亏钱

算法流程

遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）

设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1]
当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 0 或为负，则直接跳过；
遍历完成后，返回总利润 profit

复杂度分析

时间复杂度O(N): 只需遍历一次price
空间复杂度O(1): 变量使用常数额外空间

const maxProfit = function(prices) {
    let ans = 0;
    let len = prices.length;
    for (let i = 1; i < len; i++) {
        ans += Math.max(0, prices[i] - prices[i - 1]);
    }
    return ans;
}
let prices = [7, 1, 5, 3, 6, 4];
console.log(`贪心算法：${maxProfit(prices)}`);