算法题：53. 最大子数组和（动态规划）Java & Python 实现-CSDN博客

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]))  # -1

3、动态规划解法-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、完整题目

53. 最大子数组和

给你一个整数数组 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) 的解法尝试使用更为精妙的 分治法 求解。