**一. 题目描述**
Say you have an array for which the i-th 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).
**二. 题目分析**
该题是买卖股票的第二题。题目给出的基本信息没什么变化,与第一题不同的是的,允许进行任意次数的买卖,但必须保证买卖一次后才能进行第二次操作。继续分析会发现,这实际上是求股价数组所有上升段的和。
**三. 示例代码**
~~~
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int> &prices) {
int result = 0;
int i = 0;
int len = prices.size();
if(len <= 1) return 0;
for(i = 1; i < len; ++i)
{
if (prices[i] > prices[i - 1])
result += prices[i]-prices[i - 1];
}
return result;
}
};
~~~
**四. 小结**
与该题相关的题目还有好几道。后续更新…
- 前言
- 2Sum
- 3Sum
- 4Sum
- 3Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Search in Rotated Sorted Array
- Remove Element
- Merge Sorted Array
- Add Binary
- Valid Palindrome
- Permutation Sequence
- Single Number
- Single Number II
- Gray Code(2016腾讯软件开发笔试题)
- Valid Sudoku
- Rotate Image
- Power of two
- Plus One
- Gas Station
- Set Matrix Zeroes
- Count and Say
- Climbing Stairs(斐波那契数列问题)
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle 2
- Integer to Roman
- Roman to Integer
- Valid Parentheses
- Reorder List
- Path Sum
- Simplify Path
- Trapping Rain Water
- Path Sum II
- Factorial Trailing Zeroes
- Sudoku Solver
- Isomorphic Strings
- String to Integer (atoi)
- Largest Rectangle in Histogram
- Binary Tree Preorder Traversal
- Evaluate Reverse Polish Notation(逆波兰式的计算)
- Maximum Depth of Binary Tree
- Minimum Depth of Binary Tree
- Longest Common Prefix
- Recover Binary Search Tree
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Binary Tree Zigzag Level Order Traversal
- Sum Root to Leaf Numbers
- Anagrams
- Unique Paths
- Unique Paths II
- Triangle
- Maximum Subarray(最大子串和问题)
- House Robber
- House Robber II
- Happy Number
- Interlaving String
- Minimum Path Sum
- Edit Distance
- 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
- Decode Ways
- N-Queens
- N-Queens II
- Restore IP Addresses
- Combination Sum
- Combination Sum II
- Combination Sum III
- Construct Binary Tree from Inorder and Postorder Traversal
- Construct Binary Tree from Preorder and Inorder Traversal
- Longest Consecutive Sequence
- Word Search
- Word Search II
- Word Ladder
- Spiral Matrix
- Jump Game
- Jump Game II
- Longest Substring Without Repeating Characters
- First Missing Positive
- Sort Colors
- Search for a Range
- First Bad Version
- Search Insert Position
- Wildcard Matching