**
**
个人理解就是，把一个问题转换成若干个子问题并且每个子问题之间相互独立，与父问题类型相同。求文章来解决股票问题中的最大利润问题。
首先根据价格来求出每一天卖出利润，然后求出在这个利润中的索引中间值，中间值mid，假设买入的天数为start，卖出的天数为end，那么就有三种可能： （1）最大利润在start到mid之间 （2）最大利润在mid到end之间 （3）最大利润在start到end之间
然后根据递归来反复调用把一个问题转化成若干个子问题
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 最大子数组 { class Program { struct SubArry { public int start; public int end; public int total; } static void Main(string[] args) { int[] priceArry = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106,101, 79, 94, 90, 97 }; int[] profit = new int [priceArry.Length-1]; for(int i=1;i<priceArry.Length;i++) { profit[i-1] = priceArry[i] - priceArry[i-1]; } SubArry subArry = SelectSubArry(0, profit.Length - 1,profit); Console.WriteLine(subArry.start); Console.WriteLine(subArry.end); Console.WriteLine("在{0}天入 {1}天出利润最大", subArry.start, subArry.end + 1); Console.ReadKey(); } static SubArry SelectSubArry(int start,int end,int []arry) { if (start == end) { SubArry subArry4; subArry4.total = arry[start]; subArry4.start = start; subArry4.end = end; return subArry4; } int mid = (start + end) / 2; int total1 = arry[start]; int total2 = arry[mid + 1]; int totalTemp = 0; int startIndex=start; int endIndex=mid+1; SubArry subArry1 = SelectSubArry(start, mid, arry); SubArry subArry2 = SelectSubArry(mid+1, end, arry); for (int i = mid; i >= start; i--) { totalTemp += arry[i]; if (totalTemp > total1) { startIndex = i; total1 = totalTemp; } } totalTemp = 0; for (int j = mid + 1; j < arry.Length; j++) { totalTemp += arry[j]; if (totalTemp > total2) { endIndex = j; total2 = totalTemp; } } SubArry subArry3; subArry3.start = startIndex; subArry3.end = endIndex; subArry3.total = total1 + total2; if(subArry1.total>subArry2.total&&subArry1.total>subArry3.total) { return subArry1; } else if(subArry2.total>subArry1.total&&subArry2.total>subArry3.total) { return subArry2; } else { return subArry3; } } } }