题目来源:53. Maximum Subarray - LeetCode
题目难度:Easy
题目
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
1 | Input: [-2,1,-3,4,-1,2,1,-5,4], |
解答1[Java]
1 | class Solution { |
思路
动态规划。dp[i]
中存储的是 i
之前的最大的子序列和。
时间复杂度 $O(n)$,空间复杂度为 $O(n)$。
解答2[Java]
1 | class Solution { |
思路
一直加,用 curSum
表示截至目前的最大正子序和。
时间复杂度 $O(n)$,空间复杂度 $O(1)$。