menu Home Tags Archives Video About
分治算法解决问题再回顾

一言加载中...

什么是分治思想呢?

对于一个规模为N的问题,如果该问题能够直接解决,就直接解决;否则就将此问题分解为K个与原问题形式相同的子问题,通过递归的方式求解子问题,通过整合子问题从而解决原问题的策略就是分治思想(或分治策略)

分治法求最大子数组

问题描述:

现在呢有17天的股票价格数据,问在哪天买入,哪天卖出才能使收益最高?

problem

解决方案一(暴力求解)

逐个求解,比较获得最大值的那一组,实现过程省略,参考:我的博文算法-最大字串和

解决方案二(分治)

思想

  1. 计算出每天的价格波动表如下:

cal

  1. 将数据从中间分为左右两部分。此时有三种情况:
    • 买入天数在左侧部分,卖出天数在左侧部分(此时与原问题相似,递归的解决)
    • 买入天数在右侧部分,卖出天数在右侧部分(此时与原问题相似,递归的解决)
    • 买入天数在左侧部分,卖出天数在右侧部分(可直接解决)
  2. 上代码
    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);
}

这里似乎需要一个结果:

result

TonyChenn
2018.10.17

评论