题目
剑指 Offer 63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例：
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 复制代码
分析
股票问题也是个经典的动态规划类型题
还是按照动态规划的解题步骤来
- 定义 dp 数组
dp[n] 表示第n天卖出获取利润， m 表示第 m 天买入价格最低 （j < i）
- 写出状态转移方程
dp[n] = prices[n] - prices[m] (if dp[n] < 0 => m = n)
- 迭代求解 dp 数组
- 求出 dp 数组的最大值
实现
function maxProfit(prices: number[]): number { let dp: number[] = [] dp[0] = - prices[0] let minIdx: number = 0 let i: number = 1 while(i < prices.length) { dp[i] = prices[i] - prices[minIdx] if (dp[i] < 0) { minIdx = i } i ++ } let res = Math.max(...dp) return res > 0 ? res : 0 }; 复制代码
题目
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 复制代码
分析
这道题一开始做的时候有点懵，卡在了dp数组的定义上，后来看了解析才知道自己总想一步到位把问题变复杂了
除开动态规划的解题思路，还要合理的设计最终的返回值
本题的最终返回值不是直接从 dp 数组中取，而是在 dp 数组中找一个最大值，理解了这一点就简单了
- 定义 dp 数组
dp[i] 表示以 i 下标结尾的和最大字数组的值
- 写出 dp 状态转移方程
dp[n] = max{dp[n-1] + nums[n], nums[n]}
- 初始化 dp 数组
dp[0] = nums[0]
- 迭代求解 dp 数组
- 求出 dp 数组中的最大值
最终结果 max{dp[0],...,dp[n]}
实现
function maxSubArray(nums: number[]): number { let dp: number[] = [] dp[0] = nums[0] let i: number = 1 while(i < nums.length) { dp[i] = Math.max(dp[i-1]+nums[i], nums[i]) i ++ } return Math.max(...dp) };
