动态规划

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000

  /**      * 动态规划：      * 1、假设以第k个为结束点的最大字序和为F[k],显然，有以下结论：      * 2、F[k]= max(F[k-1]+nums[k],nums[k])      *      * @param nums nums      * @return res      */     public static int maxSubArray(int[] nums) {         if(nums.length ==1)return nums[0];         int[] dp = new int[nums.length]; // dp[k]代表第k个最大字序和         int res =dp[0]= nums[0];          for(int i=1;i< nums.length;i++){             dp[i] = Math.max(nums[i],dp[i-1]+nums[i]); // dp[i]代表第i个最大字序和，它是由前一个最大字序和和nums[i]比较得来的             res = res>=dp[i]?res:dp[i]; // 记录最大字序和         }         return res;     }