【lintcode】最大子数组

￡神魔★判官ぃ 2022-06-02 21:08 144阅读 0赞

题目描述：
    给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
    子数组最少包含一个数
    
    样例
    给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6

## 解法一：分治法 O(nlgn) ##

我们将一个数组分为两部分，关于它的最大子数组存在如下三种情况：  
1.最大子数组属于第一部分 2.属于第二部分 3.横跨两个部分  
所以我们只需将这三个可能的值求出来，它们中的最大值即为最大子数组之和。

int solve1(vector<int> &nums, int l, int r){ 
            if(l > r)
                return 0;
            if(l == r)
                return nums[l];
            int m = (l+r)/2;
            int maxsuml = nums[m];
            int maxsumr = nums[m+1];
            int sum = 0;
    
            for(int i = m; i >= l; i--){
                sum += nums[i];
                if(sum > maxsuml)
                    maxsuml = sum;
            }
            sum = 0;
            for(int i = m + 1; i <= r; i++){
                sum += nums[i];
                if(sum > maxsumr)
                    maxsumr = sum;
            }
    
            return max3(maxsuml + maxsumr, solve2(nums, l, m), solve2(nums, m+1, r));
        }
    
    int max3(int a, int b, int c){
            if(a >= b && a >= c)
                return a;
            //return max3(b, c, a); //这样写法简洁，但是递归效率低
    
            if(b >= c && b >= a)
                return b;
            if(c >= b && c >= a)
                return c;
        }

--------------------

## 解法二：迭代 O(n) ##

对于一个数组a\[n\], 它的最大子数组一定是以数组的第0～(n-1)个元素中的一个为结尾的，那么对于数组的第i个元素，我们能够求出以这个元素为结尾的最大子数组，求法如下：  
1.如果以a\[i-1\]结尾的最大子数组之和小于0，那么a\[i\]结尾的最大子数组之和为a\[i\]自身  
2.否则a\[i\]结尾的最大子数组之和为a\[i-1\]结尾的最大子数组之和加上a\[i\]  
由此，我们只需遍历整个数组，求出以每个元素结尾的最大子数组之和中的最大值即为最终的结果。

int solve2(vector<int> &nums){
            int maxsum, maxhere;
            maxsum = maxhere = nums[0];
            for(int i = 1; i < nums.size(); i++){
                if(maxhere > 0)
                    maxhere = nums[i] + maxhere;
                else
                    maxhere = nums[i];
                if(maxhere > maxsum)
                    maxsum = maxhere;
            }
            return maxsum;
        }

## 解法三：动态规划 O(n) ##

根据解法二的思路可得如下递推公式  
`f(n) = a[n] + max(f(n-1), 0)`  
其中f(n)表示以第n个元素结尾的最大子序列和。

int solve3(vector<int> &nums){
            int f[nums.size()];
            int maxsum = f[0] = nums[0];
            for(int i = 1; i < nums.size(); i++){
                if(f[i-1] < 0)
                    f[i] = nums[i];
                else
                    f[i] = f[i-1] + nums[i];
                if(f[i] > maxsum)
                    maxsum = f[i];
            }
            return maxsum;
        }