53. Maximum Subarray

题目描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

题解

暴力解法

两层for循环嵌套解题

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  4.         max_sum = nums[0]
  5.         for i in range(len(nums)):
  6.             sum_i = nums[i]
  7.             sum_i_max = sum_i
  8.             for j in range(i+1,len(nums)):
  9.                 sum_i += nums[j]
  10.                 sum_i_max = max(sum_i_max, sum_i)
  12.             max_sum = max(max_sum, sum_i_max)
  14.         return max_sum

扎心直接超时~
image.png

动态规划解法

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  4.         max_sum = nums[0]
  5.         pre = 0
  7.         for num in nums:
  8.             pre = max(pre+num, num)
  9.             max_sum = max(pre, max_sum)
  11.         return max_sum

貌似动态规划的解法还挺慢的，不知道是服务器现在负载很大的原因导致很慢，还是算法很慢的原因。
image.png

相关题目

最长子序列