小和问题...

小和:一个数据或者列表中的左边比他小的数据的和
可以理解为归并排序,拆分的子数组,左边是他前面的数据,右边是他自己组成的数据
为了保证复用(每次求完毕下个数复用前面的),由于数组的长度固定,使用list来储存前面的归并有序数据

public ArrayList sumSmall(int[] a) {

    ArrayList left = new ArrayList<>();

    linkedBlockingDeque right = new linkedBlockingDeque<>();
    //将数组拆分为2个列表
    left.add(a[0]);
    for (int i = 1; i < a.length; i++) {
        right.add(a[i]);
    }

    return sortAndGetSum(left, right);
}

public ArrayList sortAndGetSum(ArrayList left, linkedBlockingDeque right) {
    ArrayList res = new ArrayList<>();
    //初始化首位为0
    res.add(0);


    //优化:定义一个变量记录left的和,left有序,看最值小于头0,大于尾部sum
    int size = right.size();
    for (int r = 0; r < size; r++) {

        Integer tmp = 0;
        Integer tmpI = right.poll();
        int lSize = left.size();
        for (int i = 0; i < lSize; i++) {
            Integer integer = left.get(i);
            //左边比他小就算小和
            if (integer < tmpI) {
                tmp += integer;
            } else {
                //碰到大于等于即可跳出求和
                res.add(tmp);
                //将当前求小和放入排序队列
                left.add(i, tmpI);
                break;
            }

            //前面的都比他小末尾添加
            if (i == left.size() - 1) {
                res.add(tmp);
                left.add(tmpI);
            }
        }
    }

    return res;
}