Constfunction maxSubArray(nums: number[]): number {
// 1、dp[i]: 以第i个元素为结尾的子数组的最大和为dp[i]
// 2、递推公式：
// dp[i] = max(dp[i-1] + nums[i], nums[i])
// 即：对于每个位置，我们有两个选择：
// 1) 接续前面的子数组：dp[i-1] + nums[i]
// 2) 从当前位置重新开始：nums[i]
// 取这两种情况中的最大值
// 3、dp初始化
// dp[0] = nums[0]
const dp: number[] = [];
dp[0] = nums[0];
let max = dp[0];
for (let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(dp[i], max);
}
return max;
};
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