买卖股票的最佳时机 II

  • 4 min read
  • Tags: 
  • leetcode

一 问题描述

给定一个数组，查找数组中所有存在的元素对，使得元素对差值（后一个元素减去前一个的值）和最大。元素对之间不相交，求所有元素对的最大差值和。

122. 买卖股票的最佳时机 II

二 解决方法

1 贪心法

分析

直接找出所有最优元素对十分困难，不妨换种思路——找最小范围元素对。

计算所有最小范围的元素对（即相邻元素，这是十分简单能找到的）的最优差值，累加这些差值即可得到最大差值和，所以关键是如何确保相邻元素差值最优。

因为元素对可以只有一个元素，因此可以确保差值最小值必大于等于0，也就是说累加所有相邻元素的差值和0的较大者，即可获得最大差值和。

代码

  • 初始化最大差值和为0

  • 从第二个元素开始遍历数组

  • 比较相邻元素（当前元素值减去前面的元素值）和0的大小，将较大者累加入最大差值中去

  • 返回最大差值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0, len = prices.size();					// 初始化最大差值和为0；记录数组大小（用于遍历）
        for (int i = 1; i < len; ++i) {						// 从第二个元素开始循环（因为需要计算相邻元素差）
            ret += max(0, prices[i] - prices[i - 1]);		// 将相邻元素差与0中对较大者累加入最大差值
        }
        return ret;											// 返回最大差值和
    }
};

2动态规划

分析

仍然考虑由局部最优推倒出全局最优。

从数组的第一个元素开始，存在两种状态：一是可以将其作为元素对的起始、二是将其作为元素对的结束（后面将简记为起始状态和结束状态），同时记录两种状态下的解：起始状态解是0，终止状态解是当前元素值的负数（假定后面一定能找到一个元素与其组成元素对，因此解是负数）。

对于下一个元素，其状态也可以是起始或结束，且只与前一个元素的状态有关，计算下一个元素解方法为：新状态结束解=max(旧状态结束解, 旧状态起始解 + 当前元素值)；新状态起始解=max(旧状态起始解, 旧状态结束解 - 当前元素值)，取max以确保局部最优。

以此类推，直到运行至数组的最后一个元素，即可获得两种状态下各自的全局最优解（最大差值和）。

因为最后为结束状态一定比起时状态差值和大，所以结果选结束状态更优。

代码

  • 初始化起始状态值和结束状态值

  • 遍历数组

  • 更新起始状态值和终止状态值

  • 返回最后元素结束状态下的值（最大差值和）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();							// 记录数组长度
        int dp0 = 0, dp1 = -prices[0];					// 初始化两种状态的最大差值和，0为结束状态，1为起始状态
        int newDp0, newDp1;								// 临时变量，存放当前状态的最优解
        for (int i = 0; i < n; ++i)	{					// 遍历数组
            newDp0 = max(dp0, dp1 + prices[i]);			// 计算新结束状态值
            newDp1 = max(dp1, dp0 - prices[i]);			// 计算新起始状态值
            dp0 = newDp0;								// 更新
            dp1 = newDp1;
        }
        return dp0;										// 返回最后元素结束状态下的值
    }
};

三 总结

  • 当局部最优能够推到出全局最优时，贪心算法是一种很好的思路方法。

  • 当程序出现多种状态，且状态前后相互影响时，可以尝试动态规划算法，其关键是找到状态和状态转变的方式。