best-time-to-buy-and-sell-stock-v

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>prices</code> where <code>prices[i]</code> is the price of a stock in dollars on the <code>ith</code> day, and an integer <code>k</code>.

You are allowed to make at most <code>k</code> transactions, where each transaction can be either of the following:

<ul>
	<li>
	Normal transaction: Buy on day <code>i</code>, then sell on a later day <code>j</code> where <code>i &lt; j</code>. You profit <code>prices[j] - prices[i]</code>.
	</li>
	<li>
	Short selling transaction: Sell on day <code>i</code>, then buy back on a later day <code>j</code> where <code>i &lt; j</code>. You profit <code>prices[i] - prices[j]</code>.
	</li>
</ul>

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most <code>k</code> transactions.

&nbsp;
Example 1:

<div class="example-block">
Input: prices = [1,7,9,8,2], k = 2

Output: 14

Explanation:
We can make $14 of profit through 2 transactions:

<ul>
	<li>A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.</li>
	<li>A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Explanation:
We can make $36 of profit through 3 transactions:

<ul>
	<li>A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.</li>
	<li>A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.</li>
	<li>A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= prices.length &lt;= 103</code></li>
	<li><code>1 &lt;= prices[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= prices.length / 2</code></li>
</ul>

第 158 场双周赛

biweekly-contest-158

maximumProfit

资深工程师

Best Time to Buy and Sell Stock V

Best Time to Buy and Sell Stock

best-time-to-buy-and-sell-stock

买卖股票的最佳时机

Array

Dynamic Programming

给你一个整数数组 <code>prices</code>，其中 <code>prices[i]</code> 是第 <code>i</code> 天股票的价格（美元），以及一个整数 <code>k</code>。

你最多可以进行 <code>k</code> 笔交易，每笔交易可以是以下任一类型：

<ul>
	<li>
	普通交易：在第 <code>i</code> 天买入，然后在之后的第 <code>j</code> 天卖出，其中 <code>i &lt; j</code>。你的利润是 <code>prices[j] - prices[i]</code>。
	</li>
	<li>
	做空交易：在第 <code>i</code> 天卖出，然后在之后的第 <code>j</code> 天买回，其中 <code>i &lt; j</code>。你的利润是 <code>prices[i] - prices[j]</code>。
	</li>
</ul>

注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。

通过进行&nbsp;最多 <code>k</code> 笔交易，返回你可以获得的最大总利润。

&nbsp;

示例 1:

<div class="example-block">
输入: prices = [1,7,9,8,2], k = 2

输出: 14

解释:
我们可以通过 2 笔交易获得 14 美元的利润：

<ul>
	<li>一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。</li>
	<li>一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。</li>
</ul>
</div>

示例 2:

<div class="example-block">
输入: prices = [12,16,19,19,8,1,19,13,9], k = 3

输出: 36

解释:
我们可以通过 3 笔交易获得 36 美元的利润：

<ul>
	<li>一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。</li>
	<li>一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。</li>
	<li>一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。</li>
</ul>
</div>

&nbsp;

提示:

<ul>
	<li><code>2 &lt;= prices.length &lt;= 103</code></li>
	<li><code>1 &lt;= prices[i] &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= prices.length / 2</code></li>
</ul>