蠡口 53 Maximum Subarray 如何用 Divide&Conquer？
roundRobin · 2019-01-06 14:01:05 +08:00 · 2611 次点击这是一个创建于 2433 天前的主题，其中的信息可能已经有所发展或是发生改变。
不管怎么试都是要遍历一次然后用 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