https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
- 自己的解答
public int maxProfit(int[] prices) {
int ans = 0;
int i=0;
int j;
while(i<prices.length){
for(j=i+1;j<prices.length;j++){
if(prices[j]<=prices[j-1]){
if(j-1>i){
ans += prices[j-1]-prices[i];
}
break;
}
if(j==prices.length-1){
ans += prices[j]-prices[i];
break;
}
}
i=j;
}
return ans;
}
- 动态规划
image.png
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1;i<prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.length-1][0];
}
- 贪心
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for (int i = 1; i < n; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}
