最大子数组和

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

子数组是数组中的一个连续部分。

很经典的动态规划算法，定义状态：dp[i]为当前以i 为结尾的子数组，其最大和

dp[i]的值有两种情况，看dp[i-1] 的情况，如果为负数，那么会拖累整体 dp[i],不如就让 num[i]自己为子数组之和

因此 dp[i] = Math.max(nums[i],dp[i-1]+nums[i])

function maxSubArray(nums: number[]): number {
    if(nums.length ==1) return nums[0]
    const dp = [nums[0]]
    let max = nums[0]
    for(let i = 1;i<nums.length;i++){
        dp[i] = Math.max(nums[i],nums[i]+dp[i-1])
        max = Math.max(max,dp[i])
    }
    return max
};