最大子数组(算法)
2021-06-03 10:20:21 0 举报AI智能生成
最大子数组的算法求解
作者其他创作
大纲/内容
题目
买卖股票的最佳时机<br><br>给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。<br>如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。<br>注意你不能在买入股票前卖出股票。<br><br>示例 1:<br>输入: [7,1,5,3,6,4]<br>输出: 5<br>解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。<br>注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。<br><br>示例 2:<br>输入: [7,6,4,3,1]<br>输出: 0<br>解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。<br>
暴力求解
简单地尝试买入和卖出的时间组合，只要卖出在买入之前即可。所以运行时间也就是所有的日期组合，即O(n^2)
代码实现
分治法
我们的目的是寻找一段日期，使得第一天到最后一天的净增变值最大。我们可以把第i天的数据改为第i-1天和第i天的价格差。如果将这一行新的数据看作数组A，那么问题就可以转换成寻找A和最大非空连续子数组。我们称这样的最大非空连续子数组为最大子数组。<br><br><ul><li>求出数组的中央位置mid</li><li>然后考虑[low，mid]，[mid+1，high]两种情况, 显然[low，high]的连续子数组[i……j]必然又以下三种情况：</li></ul><span style="font-size: inherit;"> 处于[low，mid]。</span><br><span style="font-size: inherit;"> 处于[mid+1，high]。</span><br><span style="font-size: inherit;"> 跨越了中点，所以low<=i<=mid<=j<=high。<br>--------------------------------------<br></span>第一、第二种情况好处理，因为它本质上还是一个最大子数组的问题，只是规模更小，我们只需要将其递归求解即可。<br>第三种情况它加入了限制：必须包含中间位置 mid, 因此我们需要找出[low，mid]，[mid+1，high]的最大子数组，然后将它们合并即可，条件是两个最大子数组都必须包含mid。<br>
代码实现
0 条评论
下一页
