[PHP]算法-最大子数组问题思路
2023-02-18 15:47:13 时间
最大子数组问题,股票价格示例: 1.在最高价格开始向左寻找之前的最低价格 2.在最低价格开始向右寻找之后的最高价格 3.暴力求解法,尝试每队可能的买进和卖出组合,保证卖出在买进之后 key buy sell for i=0;i<n;i++ for j=i+1;j<n;j++ p=key=arr[j]-arr[i] if !key key=p if key<p buy=i sell=j 问题变化:数组A中元素连续相加最大的子数组,只有当元素有负数时才有意义 分治策略的求解思路: 1.找到数组中的中央位置mid,A[low..mid],A[mid+1..high] 2.A[low,high] 完全位于子数组A[low..mid] low<=i<=j<=mid 3.完全位于A[mid+1..high] mid<i<=j<=hign 4.跨越中点 low<=i<=mid<j<=hign 5.找出左半部分最大和(从中间到左找),找出右半部分最大和(从中间向右找) leftSum left for i=mid;i>=low;i-- sum=sum+A[i] if sum>leftSum leftSum=sum left=i rightSum right for j=mid+1;j<=high;j++ sum+=A[j] if sum > rightSum rightSum=sum right=i 6.递归调用 mid=(low+high)/2 find(A,low,mid) find(A,mid+1,high) findCross(A,low,mid,high)
相关文章
- CSS Flex 弹性布局使用
- 【stars-one】JetBrains产品试用重置工具
- JB一键重置
- 修改阿里云DNS 解决蓝奏云无法访问问题
- IDEA无限试用插件
- 油猴脚本——快速引用某篇文章的标题和地址
- lzupdate
- 封装TornadoFx常用控件库
- 蓝奏云正则字符串
- stars-one的原创工具——文档生成器
- Tornadofx学习笔记(4)——IconTextFx开源库,整合5000+个字体图标
- rpc框架dubbo学习入门及环境搭建(spring boot+Kotlin)
- Tornadofx学习笔记(3)——使用Maven编译成jar包
- 探究Spring Boot中的接收参数问题与客户端发送请求传递数据
- 提问须知
- Spring boot返回时间与MySql数据库中不相同问题及解决方法
- Spring框架学习笔记(9)——API接口设计相关知识及具体编码实现
- Tornadofx学习笔记(2)——FxRecyclerView控件的打造
- Spring框架学习笔记(8)——spring boot+mybatis plus+mysql项目环境搭建
- MySQl出现ERROR 1045 (28000): Access denied for user 'root'@'localhost'解决方法