求翻转子序列后的最大子序列和

利用前缀后缀记录到0-i和i+1到n的内部子数组最大值，然后枚举分割点

蹲

先反过来dp求以每个数为起始的最大子数组和，然后正过来dp，计算以每个位置为界的，最大子数组和，记住，这个子数组的末尾不需要是当前元素，然后再遍历，做上面两个数组的加法，这是因为你翻转本质上是把前面某个子数组拿过来相加，所以我们要找出前面最大的子数组

    Scanner sc = new Scanner(System.in);     int n = sc.nextInt();     int[] c = new int[n+2];     int[] f = new int[n+2];     int[] l = new int[n+2];     int[] r = new int[n+2];             for (int i = 1; i<= n ; i++)                     c[i] = sc.nextInt();                     for (int i= 1; i<=n ; i++){                     f[i] = Math.max(f[i-1], 0) + c[i];                     l[i] = Math.max(l[i-1], f[i]);                     }                     for(int i=n; i>=1; i--){                     f[i] = Math.max(f[i+1], 0) +c[i];                     r[i] = Math.max(r[i+1], f[i]);                     }                     int ans = l[n];                     for (int i = 1; i< n ; i++)         ans = Math.max(ans, l[i] +r[i+1]);         System.out.println(ans);

暴力过了72，懒得想了

前后缀dp

直接暴力能过73%，但最后会超时，毕竟n3

蹲一个大佬思路