最大子数组问题相关

最大子数组问题相关

问题提出

简单说来,就是在一个数组里找到子数组,使得子数组各个元素之和为最大。

问题分析

暴力解法

最为暴力的解法当然是直接遍历每一个可能的子数组,对于每一个(i,j)的子数组求和,其复杂度为O(n^2)

暴力解法代码如下:

#include<iostream>
using namespace std;
int FindMax(int * array, int n);
int main(void)
{
    int a[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
    int ans = FindMax(a, 16);
    return 0;
}
int FindMax(int * array, int n)
{
    int sum_max = -INT32_MAX;
    for(int i=0;i<n;i++)
        for (int j = i; j < n; j++)
        {
            int sum = array[i];

            for (int m = i+1; m <= j; m++)
            {
                sum += array[m];
            }
            if (sum > sum_max)
                sum_max = sum;
        }

    return sum_max;
}

基于分治策略的解法

最大的子数组一定位于一下集中情况之一

1.完全位于子数组A[low..mid]中

2.完全位于子数组A[mid..high]中

3.位于跨过中点的[i..mid..j]中

其中1、2种情况完全是规模较小的问题,所以可以使用分治策略来进行计算

对于3这种情况则可以在线性时间内求出结果,因为确定了mid这个点,就只需要求出以mid为右端点的左边最大的子数组和以mid为左端点的右边最大子数组,再将这两个子数组加在一起,就求出了跨过mid点的最大子数组

而对于其他两种情况,在分治到极限的情况,即low=high的情况,就只有一个点,直接返回就OK。

#include<iostream>
using namespace std;

int FindMax(int * array, int low, int high);
int FindCross(int * array, int low, int mid, int high);

int main(void)
{
    int a[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
    int ans = FindMax(a, 0,15);

    return 0;
}

int FindMax(int * array, int low, int high)
{
    if (high == low)
        return array[low];
    else if ((high + low) % 2 == 0)
    {
        int mid = (high + low) / 2;
        int left_sum = FindMax(array, low, mid);//求左半边最大
        int right_sum = FindMax(array, mid + 1, high);//求右半边最大
        int cross_sum = FindCross(array, low, mid, high);//求跨过中点最大

        int max_sum = left_sum;
        if (max_sum < cross_sum)
            max_sum = cross_sum;
        if (max_sum < right_sum)
            max_sum = right_sum;
        return max_sum;
    }
    else if ((high + low) % 2 == 1)
    {
        int mid = (high + low-1) / 2;
        int left_sum = FindMax(array, low, mid);
        int right_sum = FindMax(array, mid + 1, high);
        int cross_sum = FindCross(array, low, mid, high);

        int max_sum = left_sum;
        if (max_sum < cross_sum)
            max_sum = cross_sum;
        if (max_sum < right_sum)
            max_sum = right_sum;
        return max_sum;
    }
}

int FindCross(int * array, int low, int mid, int high)
{
    int left_sum =-INT32_MAX;
    int sum = 0;
    for (int i = mid;i >= low; i--)//遍历一遍mid左边
    {
        sum += array[i];
        if (sum > left_sum)
        {
            left_sum = sum;
        }
    }

    int right_sum = -INT32_MAX;
    sum = 0;
    for (int j = mid + 1; j <= high; j++)//遍历一边mid右边
    {
        sum += array[j];
        if (sum > right_sum)
            right_sum = sum;
    }

    return left_sum + right_sum;

}

容易注意到,在求Mid时使用了(low+high)%2是否为1的分类讨论,实事上可以用右移一位以达到除以2的效果,而且不需要讨论

这样杨FindMax函数则写为

int FindMax(int * array, int low, int high)
{
    if (high == low)
        return array[low];
        int mid = (high + low)>>1;
        int left_sum = FindMax(array, low, mid);
        int right_sum = FindMax(array, mid + 1, high);
        int cross_sum = FindCross(array, low, mid, high);

        int max_sum = left_sum;
        if (max_sum < cross_sum)
            max_sum = cross_sum;
        if (max_sum < right_sum)
            max_sum = right_sum;
        return max_sum;
}

线性时间算法

最大子数组问题有一个线性时间的算法

这里先给出算法

#include<iostream>
using namespace std;
int FindMax(int * array, int n);
int main(void)
{
    int a[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
    int ans = FindMax(a, 16);

    return 0;
}

int FindMax(int * array, int n)
{
    int max = array[0];//最大值
    int sum = array[0];//当前最大值
    for (int i = 1; i < n; i++)
    {
        if ((sum + array[i]) > sum)
        {

            if (sum < 0)
                sum = array[i];
            else
            {
                sum = sum + array[i];
            }
        }

        else
        {
            if (sum + array[i] > array[i])
                sum = sum + array[i];
            else
            {
                sum = array[i];
            }
        }
        if (sum > max)
            max = sum;
    }
    return max;
}

这是自己根据思想写的,但是优化空间还比较大

将重复项合并可以得到

int FindMax(int * array, int n)
{
    int max = array[0];//最大值
    int sum = array[0];//当前最大值
    for (int i = 1; i < n; i++)
    {
        if (sum > 0)//如果当前和大于0则可以加入下一个元素
            sum = sum + array[i];
        else //如果当前和小于0则扔掉。重新计sum
            sum = array[i];

        if (sum > max)
            max = sum;
    }
    return max;
}