1、解题思路
该图引用自：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
2、动态规划解法-Python代码
# 空间未做优化时的代码，保留本部分代码是为了便于理解
# class Solution:
# def maxSubArray(self, nums):
# if len(nums) == 1:
# return nums[0]
# dp = [0] * (len(nums) + 1)
# dp[0] = nums[0]
# dp[len(nums)] = nums[0]
# for i in range(1, len(nums)):
# dp[i] = max(nums[i], nums[i] + dp[i - 1])
# if dp[i] > dp[len(nums)]:
# dp[len(nums)] = dp[i]
# return dp[len(nums)]
# 空间优化1
# class Solution:
# def maxSubArray(self, nums):
# pre = 0
# res = nums[0]
# for num in nums:
# pre = max(pre + num, num)
# res = max(pre, res)
# return res
# 空间优化2
class Solution:
def maxSubArray(self, nums):
res = nums[0]
for i in range(1, len(nums)):
nums[i] += max(nums[i - 1], 0)
res = max(res, nums[i])
return res
if __name__ == '__main__':
sol = Solution()
print(sol.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(sol.maxSubArray([1])) # 1
print(sol.maxSubArray([5, 4, -1, 7, 8])) # 23
print(sol.maxSubArray([-1])) # -1
print(sol.maxSubArray([-2, -1])) # -13、动态规划解法-Java代码
public class MaxSubArray {
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));//6
System.out.println(sol.maxSubArray(new int[]{1}));//1
System.out.println(sol.maxSubArray(new int[]{5,4,-1,7,8}));//23
System.out.println(sol.maxSubArray(new int[]{-1}));//-1
System.out.println(sol.maxSubArray(new int[]{-2,-1}));//-1
}
}
//空间优化2
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
//空间优化1
//class Solution {
// public int maxSubArray(int[] nums) {
// int pre = 0;
// int res = nums[0];
// for(int num: nums){
// pre = Math.max(pre + num, num);
// res = Math.max(pre, res);
// }
// return res;
// }
//}
//空间未优化前，保留本部分代码便于理解
//class Solution {
// public int maxSubArray(int[] nums) {
// if (nums.length == 1){
// return nums[0];
// }
// int[] dp = new int[nums.length + 1];
// dp[0] = nums[0];
// dp[nums.length] = nums[0];
// for (int i = 1; i < nums.length; i++) {
// dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
// if(dp[i] > dp[nums.length]){
// dp[nums.length] = dp[i];
// }
// }
// return dp[nums.length];
// }
//}3、完整题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
