首页 > 代码库 > 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