cf Optimal Partition JAVA（dp+树状数组+前缀和+离散化）

题目链接
搞懂这个代码搞了两天，其中有些代码有些不能理解，就换了一下自己知道的算法，简单的树状数组维护最大值，就是思路有点难想，我按照自己的理解写了一点题解
代码中解释的例子的数据是

1
4
0 -2 3 -4

写的可能不是很好，有地方理解错了，希望大佬可以指出

```java
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
public class B {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        final int infinity = (int) 1e9;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int numTests = in.nextInt();
            for (int test = 0; test < numTests; test++) {
                int n = in.nextInt();
                int[] a = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = in.nextInt();
                }

                long[] s = new long[n + 1];
                for (int i = 0; i < n; i++) {
                    s[i + 1] = s[i] + a[i];
                }
                long[] sortedS = sortUnique(s);//1.将a前缀和之后去重排序的数组.离散化用

                int[] id = new int[n + 1];
                for (int i = 0; i < n + 1; i++) {
                    id[i] = Arrays.binarySearch(sortedS, s[i]);
                    //2.id是s[i]在soertedS中的下标数，1,2步骤：离散化
                    //离散化可用于优化数值大但是数量少的情况,自行搜索。
                }

                int[] d = new int[n + 1];
                Arrays.fill(d, -infinity);
                d[0] = 0;
                FenwickTreeMax ft = new FenwickTreeMax(sortedS.length+1);//建立树状数组,用树状数组来维护最大值(最小负权)。
                ft.update(id[0]+1, 0);//
                for (int i = 1; i <= n; i++) {
                    d[i] = d[i - 1] + Integer.signum(a[i - 1]);
                    //Integer.signum:如果值是负数返回-1，是0返回0,是正数返回1；
                    int temp = ft.max(id[i]-1+1)+i;
                    d[i] = Math.max(d[i], temp);
                    //d记录的是前i个的最大权
                    //ft维护的是最小负权（要知道对ft初值为Integer.min），例如：a{0,-2,3,4}.id[]={2,2,1,3,0},id的值是sorted{-3，-2,0,1}的下标.
                    //ft从下标1开始，但是后续说ft前n个都把0算进去了的！！！id的下标从0开始，ft.update(id[0]+1, 0)此时ft[3]=0;向上维护最大值（最小负权）
                    // i=1,id=2，ft前2+1个的最大值为0，
                    // i=2时，id=1,ft前1+1个的最大值为Integer.min（-1000000000）,
                    //所以d[i] = Math.max(d[i], temp)=-1;ft.update(id[i]+1, d[i]-i);此时ft{min,min,-3,0,0,}
                    //i=3,id=3,ft前4个的最大值为0，temp = 3> d=0 -> d=temp ft{min ，-2，-2，0,0}
                    //i=4,id = 0,ft前1个的最大值为min，故 d=2 > min ;
                    ft.update(id[i]+1, d[i]-i);
                }
                out.println(d[n]);
            }
        }

        private long[] sortUnique(long[] a) {
            Long[] b = new Long[a.length];
            for (int i = 0; i < a.length; i++) {
                b[i] = a[i];
            }
            Arrays.sort(b);
            int k = 0;
            for (int i = 0; i < b.length; i++) {
                if (i == 0 || !b[i].equals(b[i - 1])) {
                    b[k++] = b[i];
                }
            }
            long[] ret = new long[k];
            for (int i = 0; i < k; i++) {
                ret[i] = b[i];
            }
            return ret;
        }

        class FenwickTreeMax {
            int[] a;

            FenwickTreeMax(int n) {
                a = new int[n];
                Arrays.fill(a, -infinity);
            }

            public int lowBit(int r){
                return r&(-r);
            }
            public void update(int pos, int val) {
                while (pos 
                    a[pos] = Math.max(a[pos], val);
                    pos +=lowBit(pos);
                }
            }

            public int max(int r) {
                int res = -infinity;
                while (r > 0) {
                    res = Math.max(res, a[r]);
                    r -=lowBit(r);
                }
                return res;
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            try {
                in = new BufferedReader(new InputStreamReader(stream, "UTF-8"));
            } catch (Exception e) {
                throw new AssertionError();
            }
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}