【算法】分治

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。

适用条件

采用分治法解决的问题一般具有的特征如下：

1. 问题的规模缩小到一定的规模就可以较容易地解决。
2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。
3. 合并问题分解出的子问题的解可以得到问题的解。
4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。

设计步骤

1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。
2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。
3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。

分治法的关键是算法的组合步。究竟应该怎样合并，没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。

股票问题

从0索引开始 数组中最小的值 到 数组中最大的值 之和的一个数组
//例如 55 – 135 这段数组就是最大子数组

 //价格数组
 static int[] priceArray = { 100, 55, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97, 80, 120, 135, 90 };
 static int[] priceFluctuationArray = new int[priceArray.Length - 1];    //变化数组	

暴力求解方式

        int total = priceFluctuationArray[0];   //默认数组第一个元素是最大子数组
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < priceFluctuationArray.Length; i++)
        {
            for (int j = i; j < priceFluctuationArray.Length; j++)
            {
                int tempSum = 0;
                for (int k = i; k < j + 1; k++)
                {
                    tempSum += priceFluctuationArray[k];
                }

                if (tempSum > total)
                {
                    total = tempSum;
                    startIndex = i;
                    endIndex = j;
                }
            }
        }

        Debug.Log(string.Format("买入日期:{0} 卖出日期:{1}", startIndex, (endIndex + 1)));

分治法求解

    private SubArray FenZi(int low, int high, int[] array)
    {
        for (int i = 1; i < priceArray.Length; i++)
        {
            //变化价格 == 价格数组第i个 - 价格数据第i - 1个；
            priceFluctuationArray[i - 1] = priceArray[i] - priceArray[i - 1];
        }

        if (low == high)
        {
            SubArray subArray;
            subArray.startIndex = low;
            subArray.endIndex = high;
            subArray.total = array[low];
            return subArray;
        }

        int mid = (low + high) / 2;
        SubArray subArray1 = FenZi(low, mid, array);
        SubArray subArray2 = FenZi(mid + 1, high, array);

        int total1 = array[mid];
        int startIndex = mid;
        int temptotal = 0;
        for (int i = mid; i >= low; i--)
        {
            temptotal += array[i];
            if (temptotal > total1)
            {
                total1 = temptotal;
                startIndex = i;
            }
        }

        int total2 = array[mid + 1];
        int endIndex = mid + 1;
        temptotal = 0;
        for (int j = mid + 1; j < high; j++)
        {
            temptotal += array[j];
            if (temptotal > total2)
            {
                total2 = temptotal;
                endIndex = j;
            }
        }

        SubArray subArray3;
        subArray3.startIndex = startIndex;
        subArray3.endIndex = endIndex;
        subArray3.total = total1 + total2;
        if (subArray1.total > subArray2.total && subArray1.total > subArray3.total)
        {
            return subArray1;
        }
        else if (subArray2.total > subArray1.total && subArray2.total > subArray3.total)
        {
            return subArray2;
        }
        else
        {
            return subArray3;
        }
      }
      
    struct SubArray
    {
        public int startIndex;
        public int endIndex;
        public int total;
    }

调用

    void Start()
    {
       for (int i = 1; i < priceArray.Length; i++)
        {
             //变化价格 == 价格数组第i个 - 价格数据第i - 1个；
            //-45 55 -25 20  -3  -16 -23 18  20  -7  12  -5  -22 15  -4  7   -17 40  15 -45
            priceFluctuationArray[i-1] = priceArray[i] - priceArray[i - 1];
        }
        SubArray subArray = FenZi(0, priceFluctuationArray.Length - 1, priceFluctuationArray);
        Debug.Log(string.Format("买入日期:{0} 卖出日期:{1}", subArray.startIndex, (subArray.endIndex + 1)));
    }

来源

百度百科-分治
C#学习笔记——分治算法