2021-07-21 连续数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

简单bp

int lens = array.length;
      if(lens == 0){
          return 0;
      }
      int[] res = new int[lens];
      res[0] = array[0];
      int maxNum = res[0];
      for (int i = 1; i < lens ; i++) {
          res[i] = Math.max(res[i-1]+array[i],array[i]);
          maxNum = Math.max(res[i],maxNum);
      }
      return maxNum;