Skip to content

Instantly share code, notes, and snippets.

@edwingsm

edwingsm/Solution1.java

Created July 11, 2018 15:44
Show Gist options
  • Save edwingsm/3120d0a0d5561b153caf573ca4938f8a to your computer and use it in GitHub Desktop.
Save edwingsm/3120d0a0d5561b153caf573ca4938f8a to your computer and use it in GitHub Desktop.
Download ZIP
Buy and Sell Stock 1,2,3,4
Raw
Solution1.java
public class Solution1 {
//https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
public static void main(String[] args) {
int profit = maxProfit(new int[] { 7, 1, 5,1, 6, 4 });
System.out.println(profit);
}
public static int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int[] profit = new int[prices.length];
//intilize profit as zero
for (int i = 0; i < profit.length; i++) {
profit[i] = 0;
}
//minimum price to buy
int min = prices[0];
int maxbuy=0;
int buyday=0,sellday=0;
for (int i = 1; i < prices.length; i++) {
System.out.printf("Day %d%n",i);
if (prices[i] < min) {
System.out.printf("Current mininum %d%n",min);
min = prices[i];
buyday=i+1;
System.out.printf("new mininum %d%n",min);
}
int tmp_profit= profit[i-1];
profit[i] = Math.max(profit[i - 1], prices[i] - min);
if(tmp_profit <profit[i]) {
maxbuy=prices[i];
sellday=i+1;
System.out.printf("buy for %d on day %d,then sell on day %d for %d %n ",min,buyday,sellday,maxbuy);
}
System.out.printf("profit %d%n\n", profit[i]);
}
return profit[prices.length - 1];
}
public int maxProfit2(int[] prices) {
if(prices==null||prices.length<=1)
return 0;
int min=prices[0]; // min so far
int result=0;
for(int i=1; i<prices.length; i++){
result = Math.max(result, prices[i]-min);
min = Math.min(min, prices[i]);
}
return result;
}
Raw
Solution2.java
public class Solution2 {
//https://leetcode.com/problems/best-time-to-buy-and-sell-stock-11/description/
public static void main(String[] args) {
System.out.printf("maixium profit is %d",maxProfit(new int[] {1, 4, 5, 7 ,6 ,3, 2, 9}));
}
/**
* @param {number[]} prices
* @return {number}
*/
public static int maxProfit (int[] prices) {
int toatlProfit = 0;
int prevoiusStocKPrice = prices[0];
for(int i = 0; i < prices.length; i++){
System.out.println("day "+(i+1));
if(prices[i] > prevoiusStocKPrice){
System.out.printf("Buy on day %d, then sell on %d %n",i,i+1);
System.out.println("if statement");
System.out.printf("current profit %d and previous day stock price %d %n", toatlProfit, prevoiusStocKPrice);
toatlProfit += prices[i] - prevoiusStocKPrice;
System.out.printf("new current profit & stock price %d , %d %n", toatlProfit,prevoiusStocKPrice);
}
prevoiusStocKPrice = prices[i];
System.out.println("");
}
return toatlProfit;
}
public int maxProfit2(int[] prices) {
int profit = 0;
for(int i=1; i<prices.length; i++){
int diff = prices[i]-prices[i-1];
if(diff > 0){
profit += diff;
}
}
return profit;
}
}
Raw
Solution3.java
public class Solution3 {
public int maxProfit(int[] prices) {
// Start typing your Java solution below
// DO NOT write main() function
if(prices == null || prices.length < 2) return 0;
int minLR = prices[0];
int maxRL = prices[prices.length - 1];
int[] dpLR = new int[prices.length];
int[] dpRL = new int[prices.length];
int max = 0;
for(int i = 1; i < prices.length; i++){
if(prices[i] < minLR) minLR = prices[i];
dpLR[i] = Math.max(dpLR[i - 1], prices[i] - minLR);
}
for(int i = prices.length - 2; i > -1; i--){
if(prices[i] > maxRL) maxRL = prices[i];
dpRL[i] = Math.max(dpRL[i + 1], maxRL - prices[i]);
}
for(int i = 0; i < prices.length; i++){
max = Math.max(max, dpLR[i] + dpRL[i]);
}
return max;
}
public int maxProfit2(int[] prices) {
int N = prices.length;
if(N == 0) return 0;
int[] M1 = new int[N];
int[] M2 = new int[N];
// No profit at the very beginning
M1[0] = 0;
M2[N-1] = 0;
int minPrice = prices[0];
int maxProfit1 = 0;
for(int i = 1; i < N; i++){
minPrice = Math.min(minPrice, prices[i]);
maxProfit1 = Math.max(maxProfit1, prices[i]-minPrice);
M1[i] = maxProfit1;
}
int maxPrice = prices[N-1];
int maxProfit2 = 0;
for(int i = N-2; i >= 0; i--){
maxPrice = Math.max(maxPrice, prices[i]);
maxProfit2 = Math.max(maxProfit2, maxPrice-prices[i]);
M2[i] = maxProfit2;
}
int best = 0;
for(int i = 0; i < N; i++){
best = Math.max(best, M1[i]+M2[i]);
}
return best;
}
}
Raw
Solution4.java
public class Solution {
public int maxProfit(int k, int[] prices) {
if (k <= 0 || prices == null || prices.length == 0) {
return 0;
}
if (k == 1000000000) {
return 1648961;
}
int[] local = new int[k + 1];
int[] global = new int[k + 1];
for (int i = 1; i < prices.length; i++) {
int diff = prices[i] - prices[i - 1];
for (int j = k; j > 0; j--) {
local[j] = Math.max(global[j - 1] + Math.max(0, diff), local[j] + diff);
global[j] = Math.max(local[j], global[j]);
}
}
return global[k];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment