dp应试进阶：最大和子数组（区分：“序列”与“数组”，序列可以跳跃，数组必须连续）

力扣53

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

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

int maxSubArray(int* nums, int numsSize) {
      int dp[numsSize];
      int max=nums[0];
      for(int i=0;i<numsSize;i++)
          dp[i]=0;
          dp[0]=nums[0];
      for(int j=1;j<numsSize;j++)
      {
          if(dp[j-1]>0)//dp中保存的是nums数组前i位置子数组和的最大值
          {
            dp[j]=dp[j-1]+nums[j];  
          }
          else if(dp[j-1]<=0)//当之前的最大子数组和为负数时应当dp[j]位置直接用nums[j]代替，否则不是最大的
            dp[j]=nums[j];
            max=max<dp[j]?dp[j]:max;
      }
       return max; 
}