分治算法解决最大子数组问题

梦里梦外; 2022-03-01 01:40 204阅读 0赞

以下为股票波动价格变化表，要求求出哪一天买入哪一天卖出得到的利润最大。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMxNjgyNA_size_16_color_FFFFFF_t_70][]

这边提供两种求解方式 ：

1、暴力求解（思路简单，性能差）

思路 ：三层for循化嵌套求出每种组合的大小

static void Main(string[] args)
            {
                int[] priceArr = {100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
                int[] priceFluctuationArr = new int[priceArr.Length -1];
                SetPriceFluctuationArr(priceArr,priceFluctuationArr);
                for (int i = 0; i < priceFluctuationArr.Length; i++)
    			{
    			    Console.Write(" " + priceFluctuationArr[i]);
    			}
                Console.WriteLine();
                Violence(priceFluctuationArr);
                Console.ReadKey();
    
            }
    
            static void SetPriceFluctuationArr(int[] priceArr,int[] priceFluctuationArr)
            {
                for (int i = 0; i < priceFluctuationArr.Length; i++)
    			{
    			    priceFluctuationArr[i] = priceArr[i+1] - priceArr[i];
                    //Console.Write(" " + priceFluctuationArr[i]);
    			}
            }
    
            // 最大子数组问题
            // 暴力求解
            static void Violence(int[] priceFluctuationArr)
            {
                int len = priceFluctuationArr.Length;
                int maxPrice = 0;
                int startIndex = 0;
                int endIndex = 0;
    
                for (int i = 0; i < len; i++)
                {
                    for (int j = i; j < len; j++)
                    {
                        int tmpPrice = 0;
                        for (int index = i; index < j + 1; index++)
                        {
                            tmpPrice += priceFluctuationArr[index];
    
                        }
                        if (tmpPrice > maxPrice)
                        {
                            maxPrice = tmpPrice;
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }
    
                Console.WriteLine("startIndex:" + startIndex + " endIndex:" + endIndex + " maxPrice:" + maxPrice);
            }

2、分治法 （比较难理解，性能好）

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

思路：

![20190321141909942.png][]

1、将一个数组分成两个区间 \[low,mid\] 和 \[mid+1,high\]

2、i 、j 为最大子数组的开始索引和结束索引

i ，j 所在位置出现的情况有：

1. i j 同时位于 \[low,mid\]

2.i j 同时位于\[mid + 1,high\]

3.i 位于 \[low,mid\]，j位于\[mid + 1,high\]

再对比这三种情况下的数组 的 最大子数组，将数组一直拆分直到每个子数组个数为1为止。

a.其实第一种情况跟第二种情况 跟刚开始求 \[low,high\] 区间最大子数组的的求法是一样的 只是它们的区间变小了 ，将大区间变成小区间来求 ，这就是分治思想，将大问题一直拆分程小问题 （用递归方法）

b.第三种情况 分别取到 \[i,mid\] 取到的最大值， \[mid + 1 ,j\] 取到的最大值 ，只需求出 i跟j 的值。

**代码实现：**

class Program
        {
    
            private static int countBL = 0;    // 暴力法执行次数
            private static int countFZ = 0;    // 分治法执行次数
            static void Main(string[] args)
            {
                int[] priceArr = {100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
                int[] priceFluctuationArr = new int[priceArr.Length -1];
                SetPriceFluctuationArr(priceArr,priceFluctuationArr);
                for (int i = 0; i < priceFluctuationArr.Length; i++)
    			{
    			    Console.Write(" " + priceFluctuationArr[i]);
    			}
                Console.WriteLine();
                Violence(priceFluctuationArr);
    
    
                MaxSubArray sub = GetMaxSumArray(0,priceFluctuationArr.Length -1,priceFluctuationArr);
                Console.WriteLine("分治法  ====>" + "startIndex:" + sub.startIndex + " endIndex:" + sub.endIndex + " maxPrice:" + sub.maxPrice);
    
                Console.WriteLine("暴力法执行次数:" + countBL);
                Console.WriteLine("分治法执行次数:" + countFZ);
    
    
                Console.ReadKey();
    
            }
    
            static void SetPriceFluctuationArr(int[] priceArr,int[] priceFluctuationArr)
            {
                for (int i = 0; i < priceFluctuationArr.Length; i++)
    			{
    			    priceFluctuationArr[i] = priceArr[i+1] - priceArr[i];
                    //Console.Write(" " + priceFluctuationArr[i]);
    			}
            }
    
            // 最大子数组问题
            // 暴力求解
            static void Violence(int[] priceFluctuationArr)
            {
                int len = priceFluctuationArr.Length;
                int maxPrice = 0;
                int startIndex = 0;
                int endIndex = 0;
    
                for (int i = 0; i < len; i++)
                {
                    for (int j = i; j < len; j++)
                    {
                        int tmpPrice = 0;
                        for (int index = i; index < j + 1; index++)
                        {
                            tmpPrice += priceFluctuationArr[index];
                            countBL++; // 暴力法执行次数
                        }
                        if (tmpPrice > maxPrice)
                        {
                            maxPrice = tmpPrice;
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }
    
                Console.WriteLine("暴力法  ====>" + "startIndex:" + startIndex + " endIndex:" + endIndex + " maxPrice:" + maxPrice);
            }
    
            struct MaxSubArray {
                public int startIndex;
                public int endIndex;
                public int maxPrice;
            }
    
            // 分治算法
            static MaxSubArray GetMaxSumArray(int low,int high,int[] arr)
            {
                if (low == high)
                { 
                    MaxSubArray subArr;
                    subArr.startIndex = low;
                    subArr.endIndex = high;
                    subArr.maxPrice = arr[low];
                    return subArr;
                }
                int mid = (low + high) / 2;
    
                MaxSubArray sumArr1 = GetMaxSumArray(low, mid, arr);        // 第一种情况   i j 同时位于 [low,mid]
                MaxSubArray sumArr2 = GetMaxSumArray(mid + 1, high, arr);   // 第二种情况   i j 同时位于 [mid + 1,high]
    
    
                // 第三种情况   i 位于 [low,mid]，j位于[mid + 1,high]
                int tmpPrice = 0;
                int maxPrice = 0;
                int startIndex = mid;
                int endIndex = mid;
                // [low,mid]  求出最大子数组
                for (int i = mid; i >= low; i--)
                {
                    tmpPrice += arr[i];
                    countFZ++;       // 分治法执行次数
                    if (tmpPrice > maxPrice)
                    {
                        maxPrice = tmpPrice;
                        startIndex = i;
                    }
                }
    
                tmpPrice = 0;
                int maxPrice2 = 0;
                endIndex = mid + 1;
    
                // [mid,high]  求出最大子数组
                for (int j = mid + 1; j <= high; j++)
                {
                    tmpPrice += arr[j];
                    countFZ++;          //分治执行次数
                    if (tmpPrice > maxPrice2)
                    {
                        maxPrice2 = tmpPrice;
                        endIndex = j;
                    }
                }
    
                MaxSubArray sumArr3;
    
                sumArr3.startIndex = startIndex;
                sumArr3.endIndex = endIndex;
                sumArr3.maxPrice = maxPrice + maxPrice2;
    
                if (sumArr1.maxPrice > sumArr2.maxPrice && sumArr1.maxPrice > sumArr3.maxPrice)
                {
                    return sumArr1;
                }
                else if (sumArr2.maxPrice > sumArr1.maxPrice && sumArr2.maxPrice > sumArr3.maxPrice)
                {
                    return sumArr2;
                }
                else
                {
                    return sumArr3;
                }
    
            }
        }

运行结果： 明显看出两种算法性能伤的差别

![20190321154832701.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTMxNjgyNA_size_16_color_FFFFFF_t_70]: /images/20220301/43b4c88f372b49dda6ce1b6dd20aa6ed.png
[20190321141909942.png]: /images/20220301/e22cfb8833634a74be9d788de85829f4.png
[20190321154832701.png]: /images/20220301/d127de11580c4447bf652adbf04836ff.png