# Three O(n) algorithms from different views

• Divide and Conquer: find the left, right, and crossing maximum profit, then return the maximum of the three.
Recurrence: T(n) = 2 * T(n/2) + O(1), according to the Master method the Running time is O(n).

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0)
return 0;

Profit maxPrft = CalculateMaxProfit(prices, 0, prices.size()-1);
return maxPrft.maxProfit;
}

private:
struct Profit
{
int maxProfit; // the max profit in current portion
int maxPrice; // the highest price in current portion
int minPrice; // the lowest price in current portion

Profit(int profit, int highestPrice, int lowestPrice)
: maxProfit(profit), maxPrice(highestPrice), minPrice(lowestPrice)
{
}
};

Profit CalculateMaxProfit(const vector<int>& prices, int startIndex, int endIndex)
{
if (startIndex == endIndex)
return Profit(0, prices[startIndex], prices[startIndex]);

int midIndex = (startIndex + endIndex) / 2;
Profit left = CalculateMaxProfit(prices, startIndex, midIndex);
Profit right = CalculateMaxProfit(prices, midIndex+1, endIndex);

int maxPrft = max(left.maxProfit, right.maxProfit);
return Profit(max(maxPrft, right.maxPrice - left.minPrice),
max(left.maxPrice, right.maxPrice),
min(left.minPrice, right.minPrice));
}
};
``````

Transformation: transform the question Max(A[j] - A[i]), where j > i to question
Max((A[j] - A[j-1]) + (A[j-1]-A[j-2]) + ... + (A[i+1] - A[i])), then we can use the "53. Maximum Subarray" to solve it.

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2)
return 0;

vector<int> priceGaps;
for (int i = 1; i < prices.size(); i++)
priceGaps.push_back(prices[i] - prices[i-1]);

int maxPrft = 0;
int currPrft = 0;
for (int i = 0; i < priceGaps.size(); i++)
{
currPrft += priceGaps[i];
if (currPrft > maxPrft)
maxPrft = currPrft;

if (currPrft < 0)
currPrft = 0;
}

return maxPrft;
}
};
``````

Dynamic Programming most guys are using:

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2)
return 0;

int maxPrft = 0;
int lowestPrice = prices[0];
for (int i = 1; i < prices.size(); i++)
{
int currPrft = prices[i] - lowestPrice;
if (currPrft > maxPrft)
maxPrft = currPrft;

if (lowestPrice > prices[i])
lowestPrice = prices[i];
}

return maxPrft;
}
};``````

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