150 · Best Time to Buy and Sell Stock II - LintCode
# Description
Given an array prices , which represents the price of a stock in each day.
You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, if you already have the stock, you must sell it before you buy again).
Design an algorithm to find the maximum profit.
# Example
Example 1:
Input: [2, 1, 2, 0, 1]
Output: 2
Explanation:
1. Buy the stock on the second day at 1, and sell the stock on the third day at 2. Profit is 1.
2. Buy the stock on the 4th day at 0, and sell the stock on the 5th day at 1. Profit is 1.
Total profit is 2.
Example 2:
Input: [4, 3, 2, 1]
Output: 0
Explanation: No transaction, profit is 0.
# Code
跟之前 149 那題很像，還是考慮兩種情況
- 如果今天是最低價 ->
min = prices[i] - 如果今天的 profit 是最高 -> sum 就把 profits 加上，並且重新把今天的 min 設成今天的價位，因為還是可以今天再買，隔天再賣；（leetcode 那題是可以 same day buy and sell，這裡 lintcode 沒寫）；然後把 max 重新設 0；
buy stock 這幾題都是可以用 dp & greedy 做。
public class Solution { | |
/** | |
* @param prices: Given an integer array | |
* @return: Maximum profit | |
*/ | |
public int maxProfit(int[] prices) { | |
int sum = 0; | |
int min = Integer.MAX_VALUE; | |
int max = 0; | |
for (int i = 0; i < prices.length; i++) { | |
if (prices[i] < min) { | |
min = prices[i]; | |
} else if (prices[i] - min > max) { | |
sum += prices[i] - min; | |
min = prices[i]; | |
max = 0; | |
} | |
} | |
return sum; | |
} | |
} |
