# Java DP solution in O(n) time and O(n) space - With clear explanation in comments

• ``````public class Solution
{
public int maxProfit(int[] prices)
{
if(prices.length <= 1) return 0;

if(prices.length == 2)
{
return Math.max(0, prices[1] - prices[0]);
}

int[] changes = new int[prices.length];
changes[0] = 0;

for (int i = 1; i < changes.length; i++)
{
changes[i] = prices[i] - prices[i - 1];
}

int[] maxChange = new int[changes.length];

maxChange[0] = 0;

int maxSoFar = maxChange[0];

for (int i = 1; i < maxChange.length; i++)
{
maxChange[i] = Math.max(maxChange[i - 1] + changes[i], changes[i]);
maxSoFar = Math.max(maxSoFar, maxChange[i]);
}

return maxSoFar;
}
}

// Problem Analysis:
// Find a day i and a day j for which buying at i and selling at j give the largest profit
// In other words: find 2 elements prices[i] and prices[j] such that i < j and prices[j] - prices[i] is maximum
// We first construct an array recording the daily changes in price. Let this array be Changes.
// Changes[i] = prices[i] - prices[i - 1]
// To find the largest increase in price between 2 days, we find the contiguous subarray in Changes with the maximum sum
//
// Finding maximum subarray:
// Let maxChange(i) be the maximum sum out of all subarrays that start from the left and end at i
// For maxChange(i + 1), there are 2 possible cases:
// _ The maximum subarray at i + 1 contains only A[i + 1]
// _ The maximum subarray at i + 1 contains A[i + 1] and the maximum subarray at i
// Hence, we have: maxChange(i + 1) = max(maxChange(i) + A[i + 1], A[i + 1])
// Using this recursive relation, we can find the largest change in price (profit) in O(n) using Dynamic Programming``````

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