Skip to content

Commit 98f2999

Browse files
h2plh2pl
committed
DP
股票问题
1 parent 55e895c commit 98f2999

6 files changed

Lines changed: 132 additions & 42 deletions

‎src/DP/其他问题如股票/买入和售出股票最大的收益.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,4 +4,58 @@
44
* Created by 周杰伦 on 2018/4/9.
55
*/
66
public class 买入和售出股票最大的收益 {
7+
public static void main(String[] args) {
8+
int []a = {7, 1, 5, 3, 6, 4};
9+
int []b = {3,2,6,5,0,3};
10+
System.out.println(maxProfit(a));
11+
System.out.println(maxProfit(b));
12+
13+
}
14+
public static int maxProfit(int[] prices) {
15+
if (prices.length <= 1) {
16+
return 0;
17+
}
18+
int maxProfit = 0;
19+
int lowest = Integer.MAX_VALUE;
20+
for (int v : prices) {
21+
lowest = Math.min(v, lowest);
22+
maxProfit = Math.max(maxProfit, v - lowest);
23+
}
24+
return maxProfit;
25+
}
26+
//时间复杂度过大
27+
// public static int maxProfit(int[] prices) {
28+
// int max = 0;
29+
// for (int i = 1;i < prices.length;i ++) {
30+
// for (int j = 0;j < i;j ++) {
31+
// if (prices[i] - prices[j] > max)max = prices[i] - prices[j];
32+
// }
33+
// }
34+
// return max;
35+
// }
36+
37+
//解法太复杂
38+
// public static int maxProfit(int[] prices) {
39+
// if (prices.length == 0)return 0;
40+
// int []dp = new int[prices.length];
41+
// dp[0] = 0;
42+
// int []mins = new int[prices.length];
43+
// mins[0] = prices[0];
44+
// for (int i = 1;i < prices.length;i ++) {
45+
// if (prices[i] < mins[i - 1]) {
46+
// mins[i] = prices[i];
47+
// }else {
48+
// mins[i] = mins[i - 1];
49+
// }
50+
// }
51+
// for (int i = 1;i < prices.length;i ++) {
52+
// int min = mins[i];
53+
// if (prices[i] > min && prices[i] > prices[i - 1]) {
54+
// dp[i] = Math.max(prices[i] - min, dp[i - 1]);
55+
// }else {
56+
// dp[i] = dp[i - 1];
57+
// }
58+
// }
59+
// return dp[prices.length - 1];
60+
// }
761
}

‎src/DP/其他问题如股票/需要交易费用的股票交易_多数组.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package DP.其他问题如股票;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/4/10.
5+
*/
6+
public class 需要交易费用的股票交易_多数组 {
7+
public int maxProfit(int[] prices, int fee) {
8+
if(prices.length <= 1) return 0;
9+
int[] buy = new int[prices.length];
10+
int[] hold = new int[prices.length];
11+
int[] skip = new int[prices.length];
12+
int[] sell = new int[prices.length];
13+
// the moment we buy a stock, our balance should decrease
14+
buy[0] = 0 - prices[0];
15+
// assume if we have stock in the first day, we are still in deficit
16+
hold[0] = 0 - prices[0];
17+
for(int i = 1; i < prices.length; i++){
18+
// We can only buy on today if we sold stock
19+
// or skipped with empty portfolio yesterday
20+
buy[i] = Math.max(skip[i-1], sell[i-1]) - prices[i];
21+
// Can only hold if we bought or already holding stock yesterday
22+
hold[i] = Math.max(buy[i-1], hold[i-1]);
23+
// Can skip only if we skipped, or sold stock yesterday
24+
skip[i] = Math.max(skip[i-1], sell[i-1]);
25+
// Can sell only if we bought, or held stock yesterday
26+
sell[i] = Math.max(buy[i-1], hold[i-1]) + prices[i] - fee;
27+
}
28+
// Get the max of all the 4 actions on the last day.
29+
int max = Math.max(buy[prices.length - 1], hold[prices.length - 1]);
30+
max = Math.max(skip[prices.length - 1], max);
31+
max = Math.max(sell[prices.length - 1], max);
32+
return Math.max(max, 0);
33+
}
34+
}

‎src/DP/其他问题如股票/需要冷却期的股票交易.java‎

Lines changed: 0 additions & 41 deletions
This file was deleted.

‎src/DP/其他问题如股票/需要冷却期的股票交易_双数组.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package DP.其他问题如股票;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/4/9.
5+
*/
6+
public class 需要冷却期的股票交易_双数组 {
7+
public int maxProfit(int[] prices) {
8+
if(prices == null || prices.length < 2){
9+
return 0;
10+
}
11+
int len = prices.length;
12+
int[] sell = new int[len]; //sell[i] means must sell at day i
13+
int[] cooldown = new int[len]; //cooldown[i] means day i is cooldown day
14+
sell[1] = prices[1] - prices[0];
15+
for(int i = 2; i < prices.length; ++i){
16+
cooldown[i] = Math.max(sell[i - 1], cooldown[i - 1]);
17+
sell[i] = prices[i] - prices[i - 1] + Math.max(sell[i - 1], cooldown[i - 2]);
18+
}
19+
return Math.max(sell[len - 1], cooldown[len - 1]);
20+
}
21+
}

‎src/DP/字符串编辑/字符串复制粘贴.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package DP.字符串编辑;
2+
3+
/**
4+
* Created by 周杰伦 on 2018/4/10.
5+
*/
6+
public class 字符串复制粘贴 {
7+
public int minSteps(int n) {
8+
int[] dp = new int[n+1];
9+
10+
for (int i = 2; i <= n; i++) {
11+
dp[i] = i;
12+
for (int j = i-1; j > 1; j--) {
13+
if (i % j == 0) {
14+
dp[i] = dp[j] + (i/j);
15+
break;
16+
}
17+
18+
}
19+
}
20+
return dp[n];
21+
}
22+
}

src/DP/最长摆动子序列.java renamed to src/DP/最长摆动子序列_双数组.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
/**
44
* Created by 周杰伦 on 2018/4/4.
55
*/
6-
public class 最长摆动子序列 {
6+
public class 最长摆动子序列_双数组 {
77
public static void main(String[] args) {
88
int []a = {1,7,4,9,2,5};
99
int []b = {1,17,5,10,13,15,10,5,16,8};

0 commit comments

Comments
 (0)