LeetCode 53、最大子数组和

一、题目描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

二、题目解析

三、参考代码

1、Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        
        // 因为后面会使用到 nums 的长度
        // 所以先进行判空操作
        // 如果数组 nums 为空，返回 0
        if(nums.length == 0) return 0;

        // 获取数组的长度
        int n = nums.length;

        // 设置一个数组 dp，长度和数组 nums 长度一致
        // dp[0] 表示以第 0 个元素结尾的最大子数组的和
        // dp[1] 表示以第 1 个元素结尾的最大子数组的和
        // dp[i] 表示以第 i 个元素结尾的最大子数组的和
        int[] dp = new int[n];

        // dp[0] 表示以第 0 个元素结尾的最大子数组的和
        // 初始化 dp[0]
        dp[0] = nums[0];

        // 变量 maxNum 表示数组 dp 中最大的那个值
        // 即 maxNum 表示最大的连续字段和
        int maxNum = dp[0];

        // 从 1 开始遍历数组 nums
        for(int i = 1 ; i < n ;i++){

            // 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和
            // 如果以 nums[i-1]结尾的最大字段和为正数
            // 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 nums[i-1]结尾的最大字段和
            if(dp[i-1] > 0){
                // dp[i-1] 是正数
                // 所以 dp[i] 的值为 nums[i] 加上 dp[i-1]
                // 因为 正数 + 变量 > 变量
                // dp[i -1] + nums[i] > nums[i]
                dp[i] = dp[i -1] + nums[i];

                // 否则 dp[i-1] 不是正数，为负数或者 0
            }else{
                // 那么 dp[i] 的值为 nums[i]
                // 因为 负数 + 变量 < 变量
                // dp[i -1] + nums[i] < nums[i]
                dp[i] = nums[i];
            }
            
            // 在更新 dp[i] 的过程中，更新 maxNum 的值
            // 如果此时 dp[i] 的值大于了 maxNum
            if(maxNum < dp[i]){
                // 那么 maxNum 更新为 dp[i]
                maxNum = dp[i];
            }
        }

        // 最后返回 maxNum
        return maxNum;
    }
}

**2、**C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
         // 因为后面会使用到 nums 的长度
        // 所以先进行判空操作
        // 如果数组 nums 为空，返回 0
        if(nums.size() == 0) return 0;

        // 获取数组的长度
        int n = nums.size();

        // 设置一个数组 dp，长度和数组 nums 长度一致
        // dp[0] 表示以第 0 个元素结尾的最大子数组的和
        // dp[1] 表示以第 1 个元素结尾的最大子数组的和
        // dp[i] 表示以第 i 个元素结尾的最大子数组的和
        vector<int> dp( n , 0 );

        // dp[0] 表示以第 0 个元素结尾的最大子数组的和
        // 初始化 dp[0]
        dp[0] = nums[0];

        // 变量 maxNum 表示数组 dp 中最大的那个值
        // 即 maxNum 表示最大的连续字段和
        int maxNum = dp[0];

        // 从 1 开始遍历数组 nums
        for(int i = 1 ; i < n ;i++){

            // 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和
            // 如果以 nums[i-1]结尾的最大字段和为正数
            // 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 nums[i-1]结尾的最大字段和
            if(dp[i-1] > 0){
                // dp[i-1] 是正数
                // 所以 dp[i] 的值为 nums[i] 加上 dp[i-1]
                // 因为 正数 + 变量 > 变量
                // dp[i -1] + nums[i] > nums[i]
                dp[i] = dp[i -1] + nums[i];

                // 否则 dp[i-1] 不是正数，为负数或者 0
            }else{
                // 那么 dp[i] 的值为 nums[i]
                // 因为 负数 + 变量 < 变量
                // dp[i -1] + nums[i] < nums[i]
                dp[i] = nums[i];
            }
            
            // 在更新 dp[i] 的过程中，更新 maxNum 的值
            // 如果此时 dp[i] 的值大于了 maxNum
            if(maxNum < dp[i]){
                // 那么 maxNum 更新为 dp[i]
                maxNum = dp[i];
            }
        }

        // 最后返回 maxNum
        return maxNum;
    }
};

3、Python 代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 因为后面会使用到 nums 的长度
        # 所以先进行判空操作
        # 如果数组 nums 为空，返回 0
        if len(nums) == 0 : return 0 

        # 获取数组的长度
        n = len(nums)

        # 设置一个数组 dp，长度和数组 nums 长度一致
        # dp[0] 表示以第 0 个元素结尾的最大子数组的和
        # dp[1] 表示以第 1 个元素结尾的最大子数组的和
        # dp[i] 表示以第 i 个元素结尾的最大子数组的和
        dp = [0 for _ in range(n)]

        # dp[0] 表示以第 0 个元素结尾的最大子数组的和
        # 初始化 dp[0]
        dp[0] = nums[0] 

        # 变量 maxNum 表示数组 dp 中最大的那个值
        # 即 maxNum 表示最大的连续字段和
        maxNum = dp[0] 

        # 从 1 开始遍历数组 nums
        for i in range( 1 , n ) : 

            # 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和
            # 如果以 nums[i-1]结尾的最大字段和为正数
            # 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 nums[i-1]结尾的最大字段和
            if dp[i-1] > 0 :
                # dp[i-1] 是正数
                # 所以 dp[i] 的值为 nums[i] 加上 dp[i-1]
                # 因为 正数 + 变量 > 变量
                # dp[i -1] + nums[i] > nums[i]
                dp[i] = dp[i -1] + nums[i] 

                # 否则 dp[i-1] 不是正数，为负数或者 0
            else:
                # 那么 dp[i] 的值为 nums[i]
                # 因为 负数 + 变量 < 变量
                # dp[i -1] + nums[i] < nums[i]
                dp[i] = nums[i] 
            
            
            # 在更新 dp[i] 的过程中，更新 maxNum 的值
            # 如果此时 dp[i] 的值大于了 maxNum
            if maxNum < dp[i] :
                # 那么 maxNum 更新为 dp[i]
                maxNum = dp[i] 
    
        # 最后返回 maxNum
        return maxNum