最大连续子数组问题延伸探讨

分手后的思念是犯贱 2022-05-27 01:50 144阅读 0赞

假设存在一个这样的数组array，需要求出它的连续子数组，使得该子数组的和最大。

*  例如这样的一个数组：1, -2, 3, 10, -4, 7, 2, -5
 *  最大子数组： 3，10，-4，7，2

# 暴力法 #

不做任何优化，直接枚举所有的情况。  
思路：直接算出**array\[i,…j\]**的值

int max_sum_array(int *array, int n)
    {
        int i,j,k;
        int sum_max=0,array_sum=0;
        for(i=0;i<n;i++)
        {
            for(j=i;j<n;j++)
            {
                for(k=i;k<j;k++){
                    array_sum+=array[k];
                }
                if(array_sum>=sum_max)
                    sum_max=array_sum;
                array_sum=0;//重新计算必须清零 
            }           
        }
        return sum_max;
    }

时间复杂度为O(n3)  O ( n 3 ) ，嵌套三成循环。

# 分治法 #

这里我们将数组左分，右分开，和跨立在左右之间

int max_sep_array(int *array, int start, int end)
    {
        if(start==end)
            return array[end];
    
        int middle=(start+end)/2;
        int left_sum=max_sep_array(array,start,middle);
        int right_sum=max_sep_array(array,middle+1,end);
    
        int i,left=array[middle],now=array[middle];
        for(i=middle-1;i>=start;i--){
            now+=array[i];
            left=max(now,left);
        }
        int right=array[middle+1];
        now=array[middle+1];
        for(i=middle+2;i<=end;i++){
            now+=array[i];
            right=max(now,right);
        }
        int sum_max=right+left;
    
        return max(max(left_sum,right_sum),sum_max);
    }

这里的关键在于，当跨立在中间时，数可能是在往左一点，也可能往右一点，一定是从中间往两边发散，一定是从中间。

# 分析法 #

# 动态规划 #