# Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete **at most two transactions**.

**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

```
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 1) return 0;
int buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], sell2 = 0;
for(int i = 1; i < prices.length; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
}
```

```
//A standard dynamic approach works as well
class Solution {
public int maxProfit(int[] prices) {
int N = prices.length;
int T[][] = new int[3][N];
for(int i = 1; i <= 2; i++) {
int maxDiff = T[i-1][0] - prices[0];
for(int j = 1; j < N; j++) {
T[i][j] = Math.max(T[i][j-1], prices[j] + maxDiff);
maxDiff = Math.max(maxDiff, T[i-1][j] - prices[j]);
}
}
return T[2][N-1];
}
}
```

## Related Problems

Given a string s, partition s such that every substring of the partition is a palindrome.

Return *the ***minimum*** cuts needed for a palindrome partitioning of* s.

Given an integer array nums, return *the length of the longest ***strictly increasing subsequence**.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return *the maximum coins you can collect by bursting the balloons wisely*.