最大连续子数组以及拓展

问题描述：给定一个整数数组，数组中可能有正数、负数和零。数组中连续的一个或者多个正数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。例如，若果输入的数组为{1,-2,3，,10,-4,7,2，-5}，和最大的子数组为{3,10,-4,7,2}，应输出该子数组的和18。

解题方法一：蛮力枚举

　　用三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组和最大的一个值。

参考代码：

#include <bits/stdc++.h>

using namespace std;

int MaxSubArray( int *a, int n )
{
    int maxSum = a[0];
    int currSum = 0;
    for( int i = 0 ; i < n ; i ++ )
    {
        for( int j = i ; j < n ; j ++ )
        {
            for( int k = i ; k <= j ; k ++ )
            {
                currSum +=a[k] ;
            }
            if( currSum > maxSum )
            {
                maxSum = currSum ;
            }
            currSum = 0;
        }
    }
    return maxSum;
}

int main()
{
    int a[8]={1,-2,3,10,-4,7,2,-5};
    cout<<MaxSubArray(a,8);
}

GCC运行结果：

该方法的时间复杂度为O(n^3)

解题方法二：动态规划

　　事实上，可以令currSum是以当前元素结尾的最大连续子数组的和，maxSum是全局的最大子数组的和，当往后扫描时，对第j个元素有两种选择，要么放入前面找到的子数组，要么作为新的子数组的第一个元素：如果currSum>0,则令currSum加上a[j]，如果currsum<0，则currSum被置为当前元素，即currSum=a[j]。

　　这相当于，如果设currSum(j)是以j结尾的最大连续子数组的和，那么currSum(j)=max{0,currsum[j-1]}+a[j]。如果maxSum<currSum,则更新maxSum=currSum；否则maxSum保持原值，不更新。

　　举个例子，对于输入数组为{1,-2,3,10,-4,7,2,-5}，那么currSum和maxSum的变化分别为：

currSum： 0 -> 1 -> -1 -> 3 -> 13 -> 9 -> 16 -> 18 -> 13

maxSum:  0 -> 1 -> 1 -> 3 -> 13 -> 13 -> 16 -> 18 -> 18

参考代码：

#include <bits/stdc++.h>

using namespace std;

int MaxSubArray( int *a , int n )
{
    int currSum = 0;
    int maxSum = a[0];
    for( int j = 0 ; j < n ; j ++ )
    {
        if( currSum >= 0 )
        {
            currSum += a[j];
        }
        else
        {
            currSum = a[j];
        }
        if( currSum > maxSum )
        {
            maxSum = currSum;
        }
    }
    return maxSum;
}
int main()
{
    int a[8]={1,-2,3,10,-4,7,2,-5};
    cout<<MaxSubArray(a,8);
}

GCC运行结果：

该方法从前向后扫描数组一遍，因此该方法的时间复杂度为O(n)。

问题变形：

（1）如果要求出最大连续子数组的和，同时要求输出所求子数组的开始位置和结束位置呢？

　　解答：在解题方法一二中只需要设置开始和结束位置，每次调整数值即可。

　解题方法一：

#include <bits/stdc++.h>

using namespace std;

int MaxSubArray( int *a, int n )
{
    int maxSum = a[0];
    int currSum = 0;
    int i,j,k;
    int start = 0;
    int over = 0;
    for(i = 0 ; i < n ; i ++ )
    {
        for( j = i ; j < n ; j ++ )
        {
            for( k = i ; k <= j ; k ++ )
            {
                currSum +=a[k] ;
            }
            if( currSum > maxSum )
            {
                start = j;
                over = k;
                maxSum = currSum ;
            }
            currSum = 0;
        }
    }
     cout<<"maxSum = "<<maxSum<<" start = "<<start+1<<" over = "<<over+1<<endl;
    return maxSum;
}

int main()
{
    int a[8]={1,-2,3,10,-4,7,2,-5};
    cout<<MaxSubArray(a,8);
}

 解题方法二：

#include <bits/stdc++.h>

using namespace std;
int MaxSubArray( int *a , int n )
{
    int currSum = 0;
    int maxSum = a[0];
    int start = 0;
    int over = 0;
    for( int j = 0 ; j < n ; j ++ )
    {
        if( currSum >= 0 )
        {
            over = j;
            currSum += a[j];
        }
        else
        {
            start = j ;
            currSum = a[j];
        }
        if( currSum > maxSum )
        {
            maxSum = currSum;
        }
    }
    cout<<"maxSum = "<<maxSum<<" start = "<<start+1<<" over = "<<over+1<<endl;
    return maxSum;
}
int main()
{
    int a[8]={1,-2,3,10,-4,7,2,-5};
    int start ,over ;
    MaxSubArray(a,8);
}

（2）如果要求出最大子数组的和，但不要求子数组是连续的呢？

　解答：只需要遍历数组，如果该数大于0，则sumMAX加上该数。时间复杂度为O(n)

（3）如果数组是二维数组，同样要求出最大连续子数组的和呢？

解答：将a[0][] a[1][0]...a[n][]分别使用一位数组的方法求解出每个单位数组的最大值，对着n个最大的和进行快速排序找到最大的和

（4）如果是要求出连续子数组的最大乘积呢？