Best Time to Buy and Sell Stock

Question

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example

Given an example [3,2,3,1,2], return 1

Analysis

Time complexity: O(n). Only a single pass is needed.

Space complexity: O(1). Only two variables are used.

Solution

// Diff + Maximum Subarray

public class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int[] diff = new int[prices.length];

diff = 0;
for (int i = 1; i < prices.length; i++) {
diff[i] =  prices[i] - prices[i - 1];
}
return maxSubArray(diff);

}

public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < length; i++) {
sum = sum + nums[i];
max = Math.max(sum, max);
sum = Math.max(sum, 0);
}
return max;
}
}

One pass - record lowest price O(n) (1ms 99.88% AC)

class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) minPrice = price;
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
}

One Pass

// Only remember the lowest price

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

// Only remember the smallest price
int min = Integer.MAX_VALUE;
int profit = 0;
for (int i : prices) {
min = i < min ? i : min;
profit = (i - min) > profit ? i - min : profit;
}

return profit;
}
}

Reference

Best Time to Buy and Sell Stock Series: I, II, III, IV

LeetCode Solution