V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 2672 days ago, the information mentioned may be changed or developed.
不管怎么试都是要遍历一次然后用 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 Mar 10, 2019
小旭讲解 LeetCode 53. Maximum Subarray 分治策略
https://www.bilibili.com/video/av38950374 |
Select Language