- """
- 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.
- """"""
- 最开始的想法复杂了: 建一个 n*n 的二维数组, 存储 [i,j] 的和
- 因为最后的 output 只要和的值, 不需要求是哪些序列, 所以此想法
- 实现起来麻烦, 效率还低
- """"""
- 正确的算法应为: 贪心算法
- subMaxSum = max(nums[i]+nums[i-1], nums[i])
- nums[i] = subMaxSum
- 保证 num[i]存的是 i 之前最大的和
- """
- class Solution:
- def maxSubArray(self, nums):
- length = len(nums)
- for i in range(1, length):
- #当前值的大小与前面的值之和比较, 若当前值更大, 则取当前值, 舍弃前面的值之和
- subMaxSum = max(nums[i]+nums[i-1], nums[i])
- nums[i] = subMaxSum# 将当前和最大的赋给 nums[i], 新的 nums 存储的为和值
- return max(nums)
来源: http://www.bubuko.com/infodetail-3416964.html