Best Time to Buy and Sell Stock III
to and Time III Best Buy Stock Sell
2023-09-14 09:08:18 时间
题目
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 at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
方法
仅仅能进行两次买入卖出,非常自然的想法就是进行二分。
设数组的长度是len, A[0,..,i] ,A[i,...len - 1] 分别计算数组两部分的maxProfit,然后求和。
上述操作须要进行n次,然后返回最大的结果。显然时间复杂度(N^2)。
能够考虑使用空间换时间,从前往后遍历一遍数组,能够获取从0到i的最大maxProfit,将结果放入到数组中,
从后往前遍历一遍数组,能够获取从i到len-1的最大maxProfit,将结果放入到数组中,
遍历一遍,就能够获得结果。
public int maxProfit(int[] prices) { if (prices == null) { return 0; } int len = prices.length; if (len == 0 || len == 1) { return 0; } int[] maxPre = new int[len]; int[] maxPost = new int[len]; int min = prices[0]; int max = prices[0]; int maxPro = 0; maxPre[0] = 0; for (int i = 1; i < len; i++) { if (prices[i] > max) { max = prices[i]; int tempMaxPro = max - min; if (tempMaxPro > maxPro) { maxPro = tempMaxPro; } } else if (prices[i] < min) { min = prices[i]; max = prices[i]; } maxPre[i] = maxPro; } min = prices[len - 1]; max = prices[len - 1]; maxPro = 0; maxPost[len - 1] = 0; for (int i = len - 1; i > 0; i--) { if (prices[i - 1] > max) { min = prices[i - 1]; max = prices[i - 1]; } else if (prices[i -1] < min) { min = prices[i - 1]; int tempMaxPro = max - min; if (tempMaxPro > maxPro) { maxPro = tempMaxPro; } } maxPost[i - 1] = maxPro; } maxPro = 0; for (int i = 0; i < len; i++) { int tempMaxPro = maxPre[i] + maxPost[i]; if (maxPro < tempMaxPro ) { maxPro = tempMaxPro; } } return maxPro; }
相关文章
- How to code like a pro in 2022 and avoid If-Else
- ORA-00351: recover-to time invalid ORACLE 报错 故障修复 远程处理
- ORA-01044: size string of buffer bound to variable exceeds maximum string ORACLE 报错 故障修复 远程处理
- ORA-01258: unable to delete temporary file string ORACLE 报错 故障修复 远程处理
- ORA-26754: cannot specify both one-to-one transformation function string and one-to-many transformation function string ORACLE 报错 故障修复 远程处理
- ORA-27095: fail to get the disk sector size ORACLE 报错 故障修复 远程处理
- ORA-27152: attempt to post process failed ORACLE 报错 故障修复 远程处理
- ORA-29391: string and string must be mandatory to create a mandatory plan directive ORACLE 报错 故障修复 远程处理
- ORA-38757: Database must be mounted and not open to FLASHBACK. ORACLE 报错 故障修复 远程处理
- MySQL Error number: 3810; Symbol: ER_BINLOG_MASTER_KEY_ROTATION_FAIL_TO_CLEANUP_UNUSED_KEYS; SQLSTATE: HY000 报错 故障修复 远程处理
- MySQL Error number: MY-011169; Symbol: ER_SEMISYNC_FAILED_REGISTER_SLAVE_TO_RECEIVER; SQLSTATE: HY000 报错 故障修复 远程处理
- MySQL Error number: MY-011170; Symbol: ER_SEMISYNC_START_BINLOG_DUMP_TO_SLAVE; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-06118: NETTCP: unable to complete handshake with ORASRV ORACLE 报错 故障修复 远程处理
- ORA-06260: NETNTT: cannot write to remote process ORACLE 报错 故障修复 远程处理
- ORA-09877: sstascre: shmget error, unable to get a shared memory segment. ORACLE 报错 故障修复 远程处理
- ORA-14450: attempt to access a transactional temp table already in use ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-013831; Symbol: ER_IB_MSG_TRYING_TO_OPEN_FILE_FOR_LONG_TIME; SQLSTATE: HY000 报错 故障修复 远程处理
- 学习Oracle中的STRING_TO_TABLE函数(oracle字符串分割函数)
- Effective Methods to Tackle MySQL Database Corruption and Character Encoding Issues(解决mysql数据库乱码)
- Mastering Linux Commands: A Guide to Understanding Usage and Functions.(linux查看命令用法)
- Get Your Hands on Linux: Easy Guide to Downloading Source Code Packages(linux源码包下载)
- StepbyStep Guide to Downloading Oracle: Get Your Database System Up and Running(oracle下载教程)
- Troubleshooting Linux: Understanding the efault Error and How to Fix It(linuxefault)
- How to Fix MYSQL Error 1239 and Keep Your Database Running Smoothly(mysql1239)
- Mastering Looping in Linux: A Comprehensive Guide to For Loops(linuxfor循环)
- 10 Simple Steps to Modify MySQL and Improve Database Performance(modifymysql)
- Oracle中使用除了And的其他查询关键字(oracle中除了and)