牛客网真题2019-32-连续子数组的最大和

动态规划o(n^2) F(n)=max(F(n-1),包含第n项的连续子数组)

累加求和，从第0项开始增加，当累加和小于0时，记录此时解，累加和归0，从新开始作加法。

import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      String[] s = sc.nextLine().split(",");
      int[] in = Arrays.stream(s).mapToInt(Integer::parseInt).toArray();
      int[] res = new int[in.length + 1];
      for(int i = 1; i < res.length; i++){
          if(in[i - 1] <= 0){
              res[i] = res[i - 1];
          }else{
              int temp = 0;
              int sum = 0;
              int j = i;
              while (j > 0) {
                  sum += in[j - 1];
                  temp = Math.max(sum, temp);
                  j--;
              }
              res[i] = Math.max(res[i - 1], temp);
          }
      }
      System.out.println(res[res.length - 1]);
  }
}

累加求和法

import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      String[] s = sc.nextLine().split(",");
      int[] in = Arrays.stream(s).mapToInt(Integer::parseInt).toArray();
      int sum = 0;
      int temp = 0;
      for(int i = 0; i < in.length; i++){
          if(temp + in[i] < 0){
              sum = Math.max(temp, sum);
              temp = 0;
          }else{
              temp += in[i];
          }
      }
      System.out.println(Math.max(sum, temp));
  }
}