算法笔记-归并算法面试题、小和问题_小和问题 简单理解

1. 什么是小和问题

小和问题是指，一个数组里的元素，从左往右看，某元素的左侧有小于该元素的，就把左侧该数记下来，然后依次记录所有类型的此数，最后累加起来即为小和

举例：
数组：2 1 3 4
当元素是2时，左边无元素，不选择累加的元素
当元素是1时，左边元素是2，大于1，不选择累加的元素
当元素是3时，左边元素是2和1，都比3小，所以选择累加元素为2,1
当元素是4时，左边元素是2，1，3，都比4小，所以选择累加元素是2,1,3

总小和：2+1+2+1+3=9

2. 小和问题面试题

题目：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组【3, 2, 1, 7, 8, 9, 0】的小和

3. 对题目的思路

其实可以逆向理解题目，小和的一般算法是每一个数左边比当前数小的数累加起来，我们反过来看，只要该数的右边有数比该数大，那么该数*右边大于该数的数的数量为一部分小和

比方说，还是上面那个问题，数组：2 1 3 4，求小和
当元素是2时，右边元素1,3，4，比2大的元素有3,4，所以选择累加元素是22
当元素是1时，右边元素是3,4，大于1，所以选择累加的元素是12
当元素是3时，右边元素是4，比3大，所以选择累加元素为3*1
当元素是4时，右边无元素，所以无累加元素

总小和：22+12+3*1=9

说明这样是没有问题的

我们按逆向来理解题目，然后发现，这都是来和右侧的每一个数来比大小的，我们可以找一个算法来从左到右不遗漏的比谁大谁小，这就是归并算法

归并算法有个特点就是不断的比较大小并排序，我们可以在比较大小的时候来找到需要累加的元素，同时来进行排序方便拼合数组，目的是为了比较拼合数组时候各元素的大小

详细见下文

4. 程序

class Program
    {
   
        static void Main(string[] args)
        {
   
            int[] t = {
    3, 2, 1, 7, 8, 9, 0 };
            var p=Problem.StartSulte(t
1
2
3
4
5
6
7
8