forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStockBuySell.java
More file actions
135 lines (118 loc) · 4.11 KB
/
Copy pathStockBuySell.java
File metadata and controls
135 lines (118 loc) · 4.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package DynamicProgramming;
import java.util.Deque;
import java.util.LinkedList;
public class StockBuySellKTransactions {
public int maxProfitLinearSpace(int k, int[] prices) {
if (k == 0 || prices.length == 0) {
return 0;
}
if (k >= prices.length) {
return allTimeProfit(prices);
}
int[] T = new int[prices.length];
int[] prev = new int[prices.length];
for (int i = 1; i <= k; i++) {
int maxDiff = -prices[0];
for (int j = 1; j < prices.length; j++) {
T[j] = Math.max(T[j - 1], maxDiff + prices[j]);
maxDiff = Math.max(maxDiff, prev[j] - prices[j]);
}
for (int j = 1; j < prices.length; j++) {
prev[j] = T[j];
}
}
return T[T.length - 1];
}
public int allTimeProfit(int arr[]){
int profit = 0;
int localMin = arr[0];
for(int i=1; i < arr.length;i++){
if(arr[i-1] >= arr[i]){
localMin = arr[i];
}else{
profit += arr[i] - localMin;
localMin = arr[i];
}
}
return profit;
}
/**
* This is faster method which does optimization on slower method
* Time complexity here is O(K * number of days)
*
* Formula is
* T[i][j] = max(T[i][j-1], prices[j] + maxDiff)
* maxDiff = max(maxDiff, T[i-1][j] - prices[j])
*/
public int maxProfit(int prices[], int K) {
if (K == 0 || prices.length == 0) {
return 0;
}
int T[][] = new int[K+1][prices.length];
for (int i = 1; i < T.length; i++) {
int maxDiff = -prices[0];
for (int j = 1; j < T[0].length; j++) {
T[i][j] = Math.max(T[i][j-1], prices[j] + maxDiff);
maxDiff = Math.max(maxDiff, T[i-1][j] - prices[j]);
}
}
printActualSolution(T, prices);
return T[K][prices.length-1];
}
/**
* This is slow method but easier to understand.
* Time complexity is O(k * number of days ^ 2)
* T[i][j] = max(T[i][j-1], max(prices[j] - prices[m] + T[i-1][m])) where m is 0...j-1
*/
public int maxProfitSlowSolution(int prices[], int K) {
if (K == 0 || prices.length == 0) {
return 0;
}
int T[][] = new int[K+1][prices.length];
for (int i = 1; i < T.length; i++) {
for (int j = 1; j < T[0].length; j++) {
int maxVal = 0;
for (int m = 0; m < j; m++) {
maxVal = Math.max(maxVal, prices[j] - prices[m] + T[i-1][m]);
}
T[i][j] = Math.max(T[i][j-1], maxVal);
}
}
printActualSolution(T, prices);
return T[K][prices.length - 1];
}
public void printActualSolution(int T[][], int prices[]) {
int i = T.length - 1;
int j = T[0].length - 1;
Deque<Integer> stack = new LinkedList<>();
while(true) {
if(i == 0 || j == 0) {
break;
}
if (T[i][j] == T[i][j-1]) {
j = j - 1;
} else {
stack.addFirst(j);
int maxDiff = T[i][j] - prices[j];
for (int k = j-1; k >= 0; k--) {
if (T[i-1][k] - prices[k] == maxDiff) {
i = i - 1;
j = k;
stack.addFirst(j);
break;
}
}
}
}
while(!stack.isEmpty()) {
System.out.println("Buy at price " + prices[stack.pollFirst()]);
System.out.println("Sell at price " + prices[stack.pollFirst()]);
}
}
public static void main(String args[]) {
StockBuySellKTransactions sbt = new StockBuySellKTransactions();
int prices[] = {2, 5, 7, 1, 4, 3, 1, 3};
System.out.println("Max profit fast solution " + sbt.maxProfit(prices, 3));
System.out.println("Max profit slow solution " + sbt.maxProfitSlowSolution(prices, 3));
}
}