数组单调和

「数组单调和」，也叫「数组小和」，指的是数组中所有元素 i 的 f(i) 值之和。这里的 f(i) 函数定义为元素 i 左边（不包括其自身）小于等于它的数字之和。

举个例子，对数组 [1,3,5,2,4,6]，其数组单调和（最小和）为 27，求解过程如下。

f(arr[0]) = 0
f(arr[1]) = 1
f(arr[2]) = 1 + 3 = 4
f(arr[3]) = 1
f(arr[4]) = 1 + 3 + 2 = 6
f(arr[5]) = 1 + 3 + 5 + 2 + 4 = 15

sum = 1 + 4 + 1 + 6 + 15 = 27 

此处，以 smallSum(i) 表示数组前 i 个元素的数组单调和（最小和），观察其计算规律。

# [1]
smallSum(0) = 0;
# [1,3]
smallSum(1) = 1 = smallSum(0) + 1
# [1,3,5]
smallSum(2) = 5 = smallSum(1) + (1+3)
# [1,3,5,2]
smallSum(3) = 6 = smallSum(2) + (1)
# [1,3,5,2,4]
smallSum(4) = 12 = smallSum(3) + (1+3+2)
# [1,3,5,2,4,6]
smallSum(5) = 27 = smallSum(4) + (1+3+5+2+4)

可以发现，对数组的单调和（最小和），有如下计算公式。

smallSum(i+1) = smallSum(i) + f(arr[i+1])

f(arr[i]) 表示元素 arr[i] 左边（不包括其自身）小于等于它的数字之和

对于 f(arr[i]) 的计算，可在归并排序的 merge 阶段中计算。

举个例子，此处以数组 [1,3,5,2] 进行说明

1. smallSum = 0，表示数组单调和（最小和）
2. 对 [1] 和 [3] 进行 merge 时，发现左边元素 1 小于右边元素 3，故 smallSum += 1*1 = 1，即上文分析的 smallSum(1) = 1
3. 对 [5] 和 [2] 进行 merge 时，没有发现左边元素小于右边元素，不对 smallSum 处理
4. 对 [1,3] 和 [5,2] 进行 merge 时，发现左边元素 1 小于两个元素[5,2]，左边元素 3 小于右边 1 个元素 [5]，故 smallSum += 1*2 + 3*1 = 6，即上文分析的 smallSum(3) = 6

最后，给出使用归并排序计算数组单调和（最小和）的代码实现。

import java.util.*;

public class MonoSum {
    public int smallCount = 0;

    public int calcMonoSum(int[] A, int n) {
        mergeSort(A,n);
        return smallCount;
    }

    public void mergeSort(int[] A, int n){
        if(A == null || n <= 1){
            return;
        }
        sort(A,0,n-1);
    }

    public void sort(int[] A, int left,int right){
        if(left == right){
            return;
        }
        int mid = left + (right - left)/2;
        sort(A,left,mid);
        sort(A,mid+1,right);
        merge(A,left,mid,right);
    }

    public void merge(int[] A, int left,int mid,int right){
        int p1 = left;
        int p2 = mid+1;
        int[] tempArr = new int[right-left+1];
        int index = 0;
        while(p1 <= mid && p2 <= right){
            if(A[p1] <= A[p2]){
                //计算数组最小和
                smallCount += (right-p2+1) * A[p1]; 
                tempArr[index++] = A[p1++];
            } else {
                tempArr[index++] = A[p2++];
            }
        }
        while(p1 <= mid){
            tempArr[index++] = A[p1++];
        }
        while(p2 <= right){
            tempArr[index++] = A[p2++];
        }
        //copy data
        for(int i=0;i<tempArr.length;i++){
            A[left+i] = tempArr[i];
        }
    }
}

        }

}

暴力，性能低。

import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] data, int n) {
        // write code here
        int sum = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (data[j] <= data[i]) {
                    sum += data[j];
                }
            }
        }
        return sum;
    }
}

 public static int calcMonoSum(int[] A, int n) {
		int[] sum = new int[n];
		sum[0] = 0;
		for (int i = 1; i < n; i++) {
			if (A[i] > A[i - 1]) {
				sum[i] = sum[i - 1] + A[i - 1];
				for (int j = i - 2; j >= 0; j--) {
					if (A[j] > A[i - 1] && A[j] <= A[i]) {
						sum[i] += A[j];
					}
				}
			} else if (A[i] == A[i - 1]) {
				sum[i] = sum[i - 1] + A[i - 1];
			} else {
				int p = i - 2;
				for (; p >= 0 && A[p] > A[i]; p--){}
				if (p >= 0 && A[p] == A[i]) {
					sum[i] = sum[p] + A[p];
				} else if (p >= 0 && A[p] < A[i]) {
					sum[i] = sum[p] + A[p];
					for (int k = p - 1; k >= 0; k--) {
						if (A[k] > A[p] && A[k] <= A[i]) {
							sum[i] += A[k];
						}
					}
				}
			}
		}
		int s = 0;
		for (int i = 0; i < n; i++) {
			s += sum[i];
		}
		return s;
	}

按照DP的思想写的，计算过的一些子问题不重复计算，可是感觉不对
时间复杂度的话应该小于N方，但是自己试验了很多数据，整型并不比暴力法用时短，浮点则比暴力法用时短

public int calcMonoSum(int[] A, int n) { // write code here  int sum=0;  if(n>500) return sum;   for ( int i = 1; i <n ; i++ ) { for ( int j = i-1; j >=0 ; j-- ) { if(A[j]<=A[i]) sum+=A[j];  }
    } return sum; }

import java.util.*;
public class MonoSum {
   public int calcMonoSum(int[] A, int n) {
		int sum = 0;
		for (int i = 1; i < A.length; i ++ ) {
			int temp = 0;
			for (int j = 0; j < i; j ++ )
				if(A[j] <= A[i]) temp += A[j];
			sum += temp;
		}
		return sum;
	}
}