menu 首页 标签 归档 视频 关于
分治算法解决问题再回顾

一言加载中...

什么是分治思想呢?

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

分治法求最大子数组

问题描述:

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

problem

解决方案一(暴力求解)

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

解决方案二(分治)

思想

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

cal

  1. 将数据从中间分为左右两部分。此时有三种情况:
    • 买入天数在左侧部分,卖出天数在左侧部分(此时与原问题相似,递归的解决)
    • 买入天数在右侧部分,卖出天数在右侧部分(此时与原问题相似,递归的解决)
    • 买入天数在左侧部分,卖出天数在右侧部分(可直接解决)
  2. 上代码
//保存最大子数组数据
struct SubArray
{
    //买入天数
    public int startIndex;
    //卖出天数
    public int endIndex;
    //最大利润
    public int total;
};
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++)
    &#123;
        max2Temp += array[i];
        if(max2Temp>max2)
        &#123;
            max2 = max2Temp;
            endIndex = i;
        &#125;
    &#125;

    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;
&#125;
static void Main(string[] args)
&#123;
    int[] priceArray = &#123; 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94 &#125;;
    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);
&#125;

这里似乎需要一个结果:

result

TonyChenn
2018.10.17
写博客不易,请我喝杯咖啡?

评论

arrow_upward