首页 > 代码库 > 41. leetcode 53. Maximum Subarray
41. leetcode 53. Maximum Subarray
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4]
,
the contiguous subarray [4,-1,2,1]
has the largest sum = 6
.
思路:这个题还挺经典,在Wikipedia上有对它的详细解释,并且给出了能AC的代码。从头至尾扫描数组,设当前扫描的元素为nums[i],以max_ending_here记录结尾在元素i的连续数组的和,以max_so_far记录全程最大值,那么此时max_ending_here要么是原值加上当前值,要么是仅有当前值。
41. leetcode 53. Maximum Subarray
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。