Monday, December 28, 2015

[Leetcode] Best Time to Buy and Sell Stock III

Problem

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.

Analysis


  • 用一个数组pre记录在第i天或之前完成一个transaction的左右收益
  • 用一个数组back记录从第i天或之后开始完成一个transaction的最大收益
  • 则完成两个transactions的最大收益为 max(pre[i], back[i])


Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

No comments:

Post a Comment