动态规划

/**

• 从头开始遍历

• max为最大值，Sum为累加和

• 如果Sum+arr[i] < arr[i] => Sum < 0

• Sum = arr[i]

• 否则

• Sum += arr[i]

• 判断Sum与max的大小，更新max

• */

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  public class Main {
   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int n = Integer.parseInt(br.readLine());
       String[] line = br.readLine().split(" ");
  
       int max = Integer.parseInt(line[0]);
       int Sum = Integer.parseInt(line[0]);
       int num;
       for (int i = 1; i < n; i++) {
           num = Integer.parseInt(line[i]);
           if (Sum < 0) Sum = num;
           else Sum += num;
           if (Sum > max) max = Sum;
       }
       System.out.println(max);
   }
  }