最大子数组的和

时间:2022-05-25 18:42:40

最大子数组的和

    在给定的一个数组中,找出连续的一部分数组,使其中的元素和最大。例如输入1,-2,5,3,-3,7,-2,-1,输出的最大子数组和为12

    如果什么都不考虑,用最直接的办法来求解,即三重for循环来暴力求结果,该算法的时间复杂度为O(n^3)代码如下:

//本段代码引自编程之美
int MaxSum(int* A, int n)
{
 int maximum = -INF; 
int sum=0;   
for(int i = 0; i < n; i++)
{
 for(int j = i; j < n; j++)
{
  for(int k = i; k <= j; k++)
  {
   sum += A[k];
  }
 if(sum > maximum)
 maximum = sum;
 sum=0;
}
 }
 return maximum;
} 

    如果不需要输出最大子数组,只需要最大子数组的和的情况下,有一个时间复杂度只有O(n)的算法,下面是C语言的实现代码:

void max_sub_array(int count, int* a)
{
    int sum = a[0], t = 0;
    for (int i = 0; i < count; i++)
    {
        if (t < 0)
        {
            t = a[i];
        }
        else
        {
            t += a[i];
        }
        if (sum < t)
            sum = t;
    }
    printf("The max is %d\n", sum);
}
void main()
{
    int count, *p;
    printf("please input the count :");
    scanf_s("%d", &count);
    p = (int *)malloc(count * 2);
    printf("\nplease input the number to be sorted : \n");
    for (int i = 0; i < count; i++)
    {
        scanf_s("%d", p+i);
    }
    max_sub_array(count, p);
    system("pause");
}

    上面的这种算法,将整个数组遍历一遍,sum用来记录当前最大和,t用来记录当前正在被运算的子数组的和。如果发现t<0,则将之前算的那些子数组抛弃,从当前的a[i]开始,因为之前算的子数组和为负数,再进行下去就没有意义。如果t>0或t=0,则继续正在计算的子数组。最后判断当前子数组最大和(t)与当前最大和(sum)的大小,直到整个数组遍历完成。

    使用分治策略来解决问题的话,假设我们原数组为A[low,high],先将其分解成两个尽可能规模相同的子数组A[low,mid]和A[mid+1,high]。则原数组的任何连续的子数组A[i,j]有下面三种情况:

  • 完全在子数组A[low,mid]中,即low<=i<=j<=mid。
  • 完全在子数组A{mid+1,high]中,即mid+1<=i<=j<=high。
  • 跨越在了两个子数组之间,low<=i<=mid<=j<=high。

    因此我们只需要找出这三者并选取其中的最大者即可,算法的时间复杂度为O(n*lg(n))。下面是C语言的实现:

int max_sub_array(int from, int to, int* a)
{
    int max = 0;
    int left_max, right_max, mid_max;
    int mid_to_left_max = 0, mid_to_right_max = 0;
    int mid_to_left_sum = 0, mid_to_right_sum = 0;
    int mid = (to + from) / 2;

    if (from == to)
    {
        if (a[from] > 0)
            return a[from];
        else
            return 0;
    }

    //对问题进行分解,左边和右边分开求解最大和
    left_max = max_sub_array(from, mid, a);
    right_max = max_sub_array(mid+1, to, a);

    //对横跨中间的最大和进行处理
    for (int i = mid; i >= from;i--)
    {
        mid_to_left_sum += a[i];
        if (mid_to_left_max < mid_to_left_sum)
            mid_to_left_max = mid_to_left_sum;
    }
    for (int i = mid + 1; i <= to; i++)
    {
        mid_to_right_sum += a[i];
        if (mid_to_right_max < mid_to_right_sum)
            mid_to_right_max = mid_to_right_sum;
    }

    //将求解出的三种情况下的最大和作比较,取最大的返回
    mid_max = mid_to_left_max + mid_to_right_max;
    max = left_max;
    if (max < right_max)
        max = right_max;
    if (max < mid_max)
        max = mid_max;
    return max;
}
void main()
{
    int count, *p;
    printf("please input the count :");
    scanf_s("%d", &count);
    p = (int *)malloc(count * 2);
    printf("\nplease input the number to be sorted : \n");
    for (int i = 0; i < count; i++)
    {
        scanf_s("%d", p+i);
    }
    printf("The max is : %d.\n", max_sub_array(0, count - 1, p));
    system("pause");
}