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) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
1
2
3
4
5
Input:[1,5,11,5]
Output:true
Explanation:The arraycan be partitioned as[1,5,5]and[11].
Example 2:
1
2
3
4
5
Input:[1,2,3,5]
Output:false
Explanation:The arraycannot be partitioned into equal sum subsets.
Idea:
DP 动态规划
Solution:
Time complexity: O(n*sum)
Space complexity: O(sum)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Author: Huahua
// Running time: 16 ms
classSolution{
public:
boolcanPartition(vector<int>& nums) {
const int sum = std::accumulate(nums.begin(), nums.end(), 0);
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
1
2
3
4
Input:[7,1,5,3,6,4]
Output:5
max.difference=6-1=5(not7-1=6,asselling price needs tobe larger than buying price)
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
1
2
3
Input:cost=[10,15,20]
Output:15
Explanation:Cheapest isstart on cost[1],pay that cost andgo tothe top.
Example 2:
1
2
3
Input:cost=[1,100,1,1,1,100,1,1,100,1]
Output:6
Explanation:Cheapest isstart on cost[0],andonly step on1s,skipping cost[3].
Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].