算法（C#版）分治算法

浅浅的花香味﹌ 2022-02-27 08:42 233阅读 0赞

**分治算法**

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

可使用分治法求解的一些经典问题：

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

**分治算法** **-** **最大子数组问题**

股票问题

1，暴力求解

2，分治法

暴力求解的方法实现

using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
 
 namespace 最大子数组问题_暴力求解
 {
 class Program
 {
 static void Main(string[] args)
 {
 int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 101, 94, 106, 101, 79, 94, 90, 97 };
 int[] priceFluctuationArray = new int[priceArray.Length - 1];//价格波动的数组
 for(int i = 1; i < priceArray.Length; i++)
 {
 priceFluctuationArray[i - 1] = priceArray[i] - priceArray[i - 1];
 }
 
 int total = priceFluctuationArray[0];//默认数组的第一个元素是最大子数组
 int startIndex = 0;
 int endIndex = 0;
 
 for(int i = 0; i < priceFluctuationArray.Length; i++)
 {
 //取得以i为子数组起点的 所有子数组
 for(int j = i; j < priceFluctuationArray.Length; j++)
 {
 //由ij就确定了一个子数组
 int totalTemp = 0;//临时最大子数组的和
 for(int index =i;index < j + 1; index++)
 {
 totalTemp += priceFluctuationArray[index];
 }
 if (totalTemp > total)
 {
 total = totalTemp;
 startIndex = i;
 endIndex = j;
 }
 
 }
 }
 Console.WriteLine("startindex:" + startIndex);
 Console.WriteLine("endindex:" + endIndex);
 Console.WriteLine("购买时期是第" + startIndex + "天 出售是第" + (endIndex + 1)+"天");
 Console.ReadKey();
 }
 }
 }

![20190330100236260.png][]

分治法的实现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70][]

第三种情况遍历高低区间，找到最大的i和j

using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
 
 namespace 最大子数组问题_分治法
 {
 class Program
 {
 /// <summary>
 /// 最大子数组结构体
 /// </summary>
 struct SubArray
 {
 public int startIndex;
 public int endIndex;
 public int total;
 }
 
 static void Main(string[] args)
 {
 int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 101, 94, 106, 101, 79, 94, 90, 97 };
 int[] pf = new int[priceArray.Length - 1];//价格波动的数组
 for (int i = 1; i < priceArray.Length; i++)
 {
 pf[i - 1] = priceArray[i] - priceArray[i - 1];
 }
 
 SubArray subArray = GetMaxSubArray(0, pf.Length - 1, pf);
 Console.WriteLine(subArray.startIndex);
 Console.WriteLine(subArray.endIndex);
 Console.WriteLine(subArray.total);
 Console.WriteLine("购买时期是第" + subArray.startIndex + "天 出售是第" + (subArray.endIndex + 1) + "天");
 Console.ReadKey();
 
 }
 
 /// <summary>
 /// 这方法是取得array 这个数组 从low到high之间的最大子数组
 /// </summary>
 /// <param name="low"></param>
 /// <param name="high"></param>
 /// <param name="array"></param>
 static SubArray GetMaxSubArray(int low, int high, int[] array)
 {
 if(low == high)
 {
 SubArray subArray;
 subArray.startIndex = low;
 subArray.endIndex = high;
 subArray.total = array[low];
 return subArray;
 }
 
 int mid = (low + high) / 2;//低区间[low,middle] 高区间[middle+1,high]
 
 SubArray s1 = GetMaxSubArray(low, mid, array);
 SubArray s2 = GetMaxSubArray(mid + 1, high, array);
 //从[low,mid]找到最大子数组[i,mid]
 int total1 = array[mid];
 int startIndex = mid;
 int totalTemp = 0;
 for (int i = mid; i >= low; i--)
 {
 totalTemp += array[i];
 if (totalTemp > total1)
 {
 total1 = totalTemp;
 startIndex = i;
 }
 }
 
 //从[mid+1,high]找到最大子数组[mid+1,j]
 int total2 = array[mid + 1];
 int endIndex = mid + 1;
 totalTemp = 0;
 for (int j = mid + 1; j <= high; j++)
 {
 totalTemp += array[j];
 if (totalTemp > total2)
 {
 total2 = totalTemp;
 endIndex = j;
 }
 }
 SubArray s3;
 s3.startIndex = startIndex;
 s3.endIndex = endIndex;
 s3.total = total1 + total2;
 
 if (s1.total >= s2.total && s1.total >= s3.total)
 return s1;
 else if (s2.total >= s1.total && s2.total >= s3.total)
 return s2;
 else
 return s3;
 }
 }
 }

![20190330110242178.png][]

[20190330100236260.png]: /images/20220227/8b7168856054441aafdaa2e7b1f4ea11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvdXpodWFuamluZzE4NDk_size_16_color_FFFFFF_t_70]: /images/20220227/9af63a1254e941d48b9508055637c42b.png
[20190330110242178.png]: /images/20220227/d3659635a59d4d468cf7b9f390763d87.png