Dynamic Programming Solution - Best Time to Buy and Sell Stock III

The idea is to create an array to record max value at each element… the second loop from end to begin will find all other positive which will add to the first max value.. update if sun bigger than first max, otherwise don't.

Usually if such a problem there is no obvious way for loop with limited variables, should consider dynamic quickly….

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
return 0;
}

int result = 0;
int[] trans = new int[prices.length];
int minIndex = 0;
trans[0] = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] - prices[minIndex] > result) {
result = prices[i] - prices[minIndex];
}
if (prices[i] < prices[minIndex]) {
minIndex = i;
}
trans[i] = result;
}
result = 0;
int maxIndex = prices.length - 1;
for (int i = prices.length - 2; i >= 0; i--) {
if (prices[maxIndex] - prices[i] + trans[i] > result) {
result = prices[maxIndex] - prices[i] + trans[i];
}
if (prices[i] > prices[maxIndex]) {
maxIndex = i;
}
}
return result;
    }
}