最大子数组和（ 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
