---
# System prepended metadata

title: 0122. Best Time to Buy and Sell Stock II
tags: [Leetcode, Dynamic Programming, Medium, Greedy]

---

# 0122. Best Time to Buy and Sell Stock II
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

## 思路
### 思路一
**贪心算法 ：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法**

![](https://i.imgur.com/tHaVDcu.png)

### 思路二
动态规划
重点是找到**状态**和**状态转移函数**

![](https://i.imgur.com/A3d34NU.png)

## Code
### 思路一
```java=
class Solution {
    public int maxProfit(int[] prices) {
       int retValue = 0;
        for(int i = 0;i < prices.length-1;i++){
            retValue += prices[i+1]>prices[i]?prices[i+1]-prices[i]:0;
        }
//        System.out.println(retValue);
        return retValue;
    }
}
```
### 思路二
```java=
class Solution {
    public int maxProfit(int[] prices) {
       int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = -prices[0];
        for(int i = 1;i < prices.length;i++){
            int temp = dp[0];
            dp[0] = Math.max(dp[0],dp[1]+prices[i]);
            dp[1] = Math.max(dp[1],dp[0]-prices[i]);
//            System.out.println(dp[i][0]+" "+dp[i][1]);
        }
       return Math.max(dp[0],dp[1]);
    }
}
```
## Result
### 思路一
Runtime: 2 ms, faster than **10.75%** of Java online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 41.2 MB, less than **11.42%** of Java online submissions for Best Time to Buy and Sell Stock II.
### 思路二
Runtime: 1 ms, faster than **63.54%** of Java online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 38.5 MB, less than **74.91%** of Java online submissions for Best Time to Buy and Sell Stock II.