缤纷云 - 超高性能🚀 的智能对象存储服务
基于高度自研的架构，我们以 1/3 的成本提供最多 20+ 倍的综合性能增益（对比OSS、Qiniu等主流服务），让你的项目体验得到令人艳羡的提升。
Promoted by nicoljiang
蠡口 53 Maximum Subarray 如何用 Divide&Conquer？
roundRobin · 2019-01-06 14:01:05 +08:00 · 2613 次点击这是一个创建于 2434 天前的主题，其中的信息可能已经有所发展或是发生改变。
不管怎么试都是要遍历一次然后用 DP 来比较最大值，怎样都是 o(n)的复杂度吧？题目的意思用分治能优化吗？求解
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
 |
1
t9ouKal33vGEZyf5 2019-03-10 09:36:19 +08:00
小旭讲解 LeetCode 53. Maximum Subarray 分治策略
https://www.bilibili.com/video/av38950374 |
Select Language