# C++ 6ms (100%) solution (not DP)

•     int maxProfit(vector<int>& prices) {
int size = prices.size();
if (prices.size() <= 1) {
return 0;
}

// trans1MaxProfit[i]: starting from day0, ending at dayi, max profit
// trans2MaxProfit[i]: starting from dayi+1, ending at final day, max profit
// i = size - 1 means there is no trans2, all profits from trans1.
vector<int> trans1MaxProfit(size);
vector<int> trans2MaxProfit(size);

int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < size; i++) {
if (prices[i] > minPrice) {
int profit = prices[i] - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
} else {
minPrice = prices[i];
}
trans1MaxProfit[i] = maxProfit;
}

int maxSellPrice = prices[size - 1];
maxProfit = 0;
for (int i = size - 2; i >= 1; i--) {
if (prices[i] >= maxSellPrice) {
maxSellPrice = prices[i];
} else {
int profit = maxSellPrice - prices[i];
if (profit > maxProfit) {
maxProfit = profit;
}
}
// according to definition, trans2MaxProfit[i] starts from day i+1
trans2MaxProfit[i - 1] = maxProfit;
}

// add up trans1 and trans2 to find out the max
maxProfit = 0;
for (int i = 0; i < size; i++) {
int sum = trans1MaxProfit[i] + trans2MaxProfit[i];
if (sum > maxProfit) {
maxProfit = sum;
}
}
return maxProfit;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.