-
Preface
- FAQ
-
Part I - Basics
- Basics Data Structure
- Basics Sorting
- Basics Algorithm
- Basics Misc
-
Part II - Coding
- String
-
Integer Array
-
Remove Element
-
Zero Sum Subarray
-
Subarray Sum K
-
Subarray Sum Closest
-
Recover Rotated Sorted Array
-
Product of Array Exclude Itself
-
Partition Array
-
First Missing Positive
-
2 Sum
-
3 Sum
-
3 Sum Closest
-
Remove Duplicates from Sorted Array
-
Remove Duplicates from Sorted Array II
-
Merge Sorted Array
-
Merge Sorted Array II
-
Median
-
Partition Array by Odd and Even
-
Kth Largest Element
-
Remove Element
-
Binary Search
-
First Position of Target
-
Search Insert Position
-
Search for a Range
-
First Bad Version
-
Search a 2D Matrix
-
Search a 2D Matrix II
-
Find Peak Element
-
Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II
-
Find Minimum in Rotated Sorted Array
-
Find Minimum in Rotated Sorted Array II
-
Median of two Sorted Arrays
-
Sqrt x
-
Wood Cut
-
First Position of Target
-
Math and Bit Manipulation
-
Single Number
-
Single Number II
-
Single Number III
-
O1 Check Power of 2
-
Convert Integer A to Integer B
-
Factorial Trailing Zeroes
-
Unique Binary Search Trees
-
Update Bits
-
Fast Power
-
Hash Function
-
Happy Number
-
Count 1 in Binary
-
Fibonacci
-
A plus B Problem
-
Print Numbers by Recursion
-
Majority Number
-
Majority Number II
-
Majority Number III
-
Digit Counts
-
Ugly Number
-
Plus One
-
Palindrome Number
-
Task Scheduler
-
Single Number
-
Linked List
-
Remove Duplicates from Sorted List
-
Remove Duplicates from Sorted List II
-
Remove Duplicates from Unsorted List
-
Partition List
-
Add Two Numbers
-
Two Lists Sum Advanced
-
Remove Nth Node From End of List
-
Linked List Cycle
-
Linked List Cycle II
-
Reverse Linked List
-
Reverse Linked List II
-
Merge Two Sorted Lists
-
Merge k Sorted Lists
-
Reorder List
-
Copy List with Random Pointer
-
Sort List
-
Insertion Sort List
-
Palindrome Linked List
-
LRU Cache
-
Rotate List
-
Swap Nodes in Pairs
-
Remove Linked List Elements
-
Remove Duplicates from Sorted List
-
Binary Tree
-
Binary Tree Preorder Traversal
-
Binary Tree Inorder Traversal
-
Binary Tree Postorder Traversal
-
Binary Tree Level Order Traversal
-
Binary Tree Level Order Traversal II
-
Maximum Depth of Binary Tree
-
Balanced Binary Tree
-
Binary Tree Maximum Path Sum
-
Lowest Common Ancestor
-
Invert Binary Tree
-
Diameter of a Binary Tree
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Inorder and Postorder Traversal
-
Subtree
-
Binary Tree Zigzag Level Order Traversal
-
Binary Tree Serialization
-
Binary Tree Preorder Traversal
- Binary Search Tree
- Exhaustive Search
-
Dynamic Programming
-
Triangle
-
Backpack
-
Backpack II
-
Minimum Path Sum
-
Unique Paths
-
Unique Paths II
-
Climbing Stairs
-
Jump Game
-
Word Break
-
Longest Increasing Subsequence
-
Palindrome Partitioning II
-
Longest Common Subsequence
-
Edit Distance
-
Jump Game II
-
Best Time to Buy and Sell Stock
-
Best Time to Buy and Sell Stock II
-
Best Time to Buy and Sell Stock III
-
Best Time to Buy and Sell Stock IV
-
Distinct Subsequences
-
Interleaving String
-
Maximum Subarray
-
Maximum Subarray II
-
Longest Increasing Continuous subsequence
-
Longest Increasing Continuous subsequence II
-
Maximal Square
-
Triangle
- Graph
- Data Structure
- Big Data
- Problem Misc
-
Part III - Contest
- Google APAC
- Microsoft
- Appendix I Interview and Resume
-
Tags
Best Time to Buy and Sell Stock II
Question
- leetcode: Best Time to Buy and Sell Stock II | LeetCode OJ
- lintcode: (150) Best Time to Buy and Sell Stock II
Say you have an array for
which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit.
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, you must sell the stock before you buy again).
Example
Given an example [2,1,2,0,1], return 2
copy
题解
卖股票系列之二,允许进行多次交易,但是不允许同时进行多笔交易。直觉上我们可以找到连续的多对波谷波峰,在波谷买入,波峰卖出,稳赚不赔~ 那么这样是否比只在一个差值最大的波谷波峰处交易赚的多呢?即比上题的方案赚的多。简单的证明可先假设存在一单调上升区间,若人为改变单调区间使得区间内存在不少于一对波谷波峰,那么可以得到进行两次交易的差值之和比单次交易大,证毕。
好了,思路知道了——计算所有连续波谷波峰的差值之和。需要遍历求得所有波谷波峰的值吗?我最开始还真是这么想的,看了 soulmachine 的题解才发现原来可以把数组看成时间序列,只需要计算相邻序列的差值即可,只累加大于0的差值。
Python
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
if prices is None or len(prices) <= 1:
return 0
profit = 0
for i in xrange(1, len(prices)):
diff = prices[i] - prices[i - 1]
if diff > 0:
profit += diff
return profit
copy
C++
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
if (prices.size() <= 1) return 0;
int profit = 0;
for (int i = 1; i < prices.size(); ++i) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) profit += diff;
}
return profit;
}
};
copy
Java
class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int profit = 0;
for (int i = 1; i < prices.length; i++) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) profit += diff;
}
return profit;
}
};
copy
源码分析
核心在于将多个波谷波峰的差值之和的计算转化为相邻序列的差值,故 i 从1开始算起。
复杂度分析
遍历一次原数组,时间复杂度为 , 用了几个额外变量,空间复杂度为 .
Reference
- soulmachine 的卖股票系列