技巧1：f[i][j]占用空间过大，可以考虑f[j][i]能否优化掉一维

CF 1582 E. Pchelyonok and Segments

输入 t(t≤100) 表示 t 组数据。每组数据输入 n(1≤n≤1e5) 和长为 n 的整数数组 a (1≤a[i]≤1e9)，所有数据的 n 之和不超过 1e5。从 a 中选尽可能多的互不相交的子数组，设有 k 个子数组，需满足：
1. 从左到右第一个子数组的长度恰好是 k，第二个的长度恰好是 k-1，……，最后一个的长度恰好是 1；
2. 从左到右第 i 个子数组的元素和严格小于第 i+1 个子数组的元素和。输出 k 的最大值。注：子数组是连续的。

输入
5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7
输出
1
1
2
3
1

思路：
f[i][j]表示从i开始的后缀，最大长度为j的最小值。
然后会发现这种写法需要占用的空间太大，会MLE
考虑f[j][i]然后优化掉j这一维

  1. static final int N = 100010;
  2. static int[] a = new int[N];
  3. static long[] s = new long[N];
  4. static long[] f = new long[N], g = new long[N];
  5. static int n;
  6. static void solve() {
  7.     int T = ni();
  8.     while (T-- > 0) {
  9.         n = ni();
  10.         s[n + 1] = 0;
  11.         for (int i = 1; i <= n; i++)
  12.             a[i] = ni();
  14.         Arrays.fill(f, 0);
  15.         Arrays.fill(g, 0);
  16.         for (int i = n; i >= 1; i--) {
  17.             s[i] = s[i + 1] + a[i];
  18.             f[i] = Math.max(f[i + 1], a[i]);
  19.         }
  22.         int c = 1;
  23.         for (int k = 2; ; k++) {
  24.             g[n] = 0;
  25.             for (int i = n; i >= 1; i--) {
  26.                 g[i] = g[i + 1];
  27.                 if (i + k <= n && s[i] - s[i + k] < f[i + k])
  28.                     g[i] = Math.max(g[i], s[i] - s[i + k]);
  29.             }
  30.             long[] t = g;
  31.             g = f;
  32.             f = t;
  33.             if (f[1] == 0) break;
  34.             c++;
  35.         }
  36.         out.println(c);
  37.     }
  38. }