leetcode:Best Time to Buy and Sell Stock II
LeetCode to and II Time Best Buy Stock
2023-09-11 14:21:03 时间
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).
羞愧啊,根本不用那么复杂!直接统计每段上升序列的最大差就能够了
class Solution { public: int maxProfit(vector<int> &prices) { if( prices.size() < 2) return 0; int max_profit = 0; for( int i = 1; i < prices.size(); ++i){ if( prices[i] - prices[i-1] > 0) max_profit += prices[i] - prices[i-1]; } return max_profit; } };
(之前的做法,想太多了)
和best time to buy and sell stock的差别是同意多次买入和卖出,dp[i]保存当前能获得的最低股价
那么max_profit就须要累加prices[i]-dp[i],这就会出现反复加的情况,比方prices 1 2 4相应dp 1 1 1,会反复加,所以每次算dp[i]要修正,取最大的prices[j]-dp[j],其余的prices[j]=dp[j]
class Solution { public: int maxProfit(vector<int> &prices) { if( prices.size() < 2) return 0; vector< int> dp( prices.size(), INT_MAX); dp[0] = prices[0]; for( int i = 1; i < prices.size(); ++i){ int mini = prices[i]; for( int j = i - 1; j >= 0; --j){ if(prices[i] - dp[j] > prices[j] - dp[j]){//保证prices[i]-dp[i]最大 mini = dp[j]; dp[j] = prices[j]; if( prices[j] == dp[j]) break; } else{ break; } } dp[i] = mini; } int max_profit = 0; for( int i = 0; i < prices.size(); ++i){ max_profit = prices[i] - dp[i] > 0 ? max_profit + prices[i] - dp[i] : max_profit; } return max_profit; } };
相关文章
- Leetcode: Different Ways to Add Parentheses
- Leetcode: Best Time to Buy and Sell Stock III
- Leetcode: Minimum Window Substring
- Leetcode: String to Integer
- leetcode 114.Flatten Binary Tree to Linked List (将二叉树转换链表) 解题思路和方法
- LeetCode高频题75. 颜色分类:荷兰国旗问题
- LeetCode高频题69. x 的平方根,二分法搞定,非常简单
- [LeetCode] Best Time to Buy and Sell Stock III
- [LeetCode] Best Time to Buy and Sell Stock
- mysql更新字段值提示You are using safe update mode and you tried to update a table without a WHERE that uses a KEY column To disable safe mode
- [LeetCode]5412. 在既定时间做作业的学生人数
- [LeetCode]121. 买卖股票的最佳时机
- 2404. 出现最频繁的偶数元素(leetcode)
- 【LeetCode】122. Best Time to Buy and Sell Stock II
- LeetCode——Convert Sorted Array to Binary Search Tree
- [LeetCode] 1338. Reduce Array Size to The Half 数组大小减半
- [LeetCode] 1330. Reverse Subarray To Maximize Array Value 翻转子数组得到最大的数组值
- [LeetCode] 1309. Decrypt String from Alphabet to Integer Mapping 解码字母到整数映射
- [LeetCode] 1290. Convert Binary Number in a Linked List to Integer 二进制链表转整数
- [LeetCode] 1249. Minimum Remove to Make Valid Parentheses 移除无效的括号
- [LeetCode] 1016. Binary String With Substrings Representing 1 To N 子串能表示从1到N数字的二进制串
- [LeetCode] 973. K Closest Points to Origin 最接近原点的K个点
- [LeetCode] 960. Delete Columns to Make Sorted III 删除列使其有序之三
- [LeetCode] 944. Delete Columns to Make Sorted 删除列使其有序
- [LeetCode] All Paths From Source to Target 从起点到目标点到所有路径
- [LeetCode] IP to CIDR 将IP地址转为CIDR无类别域间路由
- [LeetCode] 623. Add One Row to Tree 二叉树中增加一行
- [LeetCode] Convert a Number to Hexadecimal 数字转为十六进制
- [LeetCode] 260. Single Number III 单独的数字之三
- [LeetCode] Best Time to Buy and Sell Stock II 买股票的最佳时间之二