题目
假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你最多只能进行两次交易(一次买进和一次卖出记为一次交易。买进和卖出均无手续费)。
请设计一个函数,计算你所能获得的最大收益。
示例1
输入:
输出:
tips:
1 2
| 第三天买进,第四天卖出,第五天买进,第六天卖出。总收益为4。 总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
|
思路
分析
该问题为动态规划问题,关键在于找到初始值以及动态规划转移方程。
实现
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
| import java.util.*;
public class Solution {
public int maxProfit (int[] prices) { if(prices.length == 0)return 0; int[][] dp = new int[prices.length][5]; dp[0][1] = -1 * prices[0]; dp[0][3] = -1 * prices[0]; for(int i = 1; i<prices.length; i++){ dp[i][0] = dp[i-1][0]; dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]); dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]); dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]); } return dp[prices.length-1][4]; } }
|