什么是分治思想呢？
对于一个规模为N的问题，如果该问题能够直接解决，就直接解决；否则就将此问题分解为K个与原问题形式相同的子问题，通过递归的方式求解子问题，通过整合子问题从而解决原问题的策略就是分治思想（或分治策略）
分治法求最大子数组
问题描述：
现在呢有17天的股票价格数据，问在哪天买入，哪天卖出才能使收益最高？
解决方案一（暴力求解）
逐个求解，比较获得最大值的那一组，实现过程省略，参考：我的博文算法-最大字串和
解决方案二（分治）
思想
- 计算出每天的价格波动表如下：
- 将数据从中间分为左右两部分。此时有三种情况：
- 买入天数在左侧部分，卖出天数在左侧部分（此时与原问题相似，递归的解决）
- 买入天数在右侧部分，卖出天数在右侧部分（此时与原问题相似，递归的解决）
- 买入天数在左侧部分，卖出天数在右侧部分（可直接解决）
- 上代码
1
2
3
4
5
6
7
8
9
10
|
struct SubArray
{
public int startIndex;
public int endIndex;
public int total;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| static SubArray GetMaxSubArray(int[] array,int start,int end)
{
if(start==end)
{
SubArray temp;
temp.startIndex = start;
temp.endIndex = end;
temp.total = array[start];
return temp;
}
int mid = (start + end) / 2;
SubArray subArray1 = GetMaxSubArray(array, start, mid);
SubArray subArray2 = GetMaxSubArray(array, mid + 1, end);
int max1 = array[mid];
int max1Temp = 0;
int startIndex = mid;
for (int i = mid; i >=start ; i--)
{
max1Temp += array[i];
if (max1Temp > max1)
{
max1 = max1Temp;
startIndex = i;
}
}
int max2 = array[mid + 1];
int max2Temp = 0;
int endIndex = mid + 1;
for (int i = mid+1; i <end; i++)
{
max2Temp += array[i];
if(max2Temp>max2)
{
max2 = max2Temp;
endIndex = i;
}
}
SubArray subArray3;
subArray3.startIndex = startIndex;
subArray3.endIndex = endIndex;
subArray3.total = max1 + max2;
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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| static void Main(string[] args)
{
int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94 };
int[] fluctuateArray = new int[priceArray.Length - 1];
for (int i = 0; i < fluctuateArray.Length; i++)
fluctuateArray[i] = priceArray[i + 1] - priceArray[i];
SubArray curr= GetMaxSubArray(fluctuateArray, 0, fluctuateArray.Length-1);
Console.WriteLine("买入天数："+curr.startIndex + " 卖出天数：" + curr.endIndex+1 + " 最大利润:" + curr.total);
}
|
这里似乎需要一个结果：
TonyChenn2018.10.17
