题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// 未优化
class Solution {
public: 
    int maxSubArray(vector<int>& nums) {
        // f[k] 表示前k个数字中最大的子数组和 
        // f[k] = max (f[k - 1] , 0) + a[k]
        int n = nums.size();
        int f[n];
        f[0] = nums[0];
        for(int i = 1 ; i < n ; i++){
            f[i] = max(f[i - 1] , 0) + nums[i];
            //cout << f[i] << " ";
        }

        sort(f , f + n, [](int a,int b){return a < b ;} );
        return f[n -1];
    }
};
//优化版本
class Solution {
public: 
    int maxSubArray(vector<int>& nums) {
        // f[k] 表示前k个数字中最大的子数组和 
        // f[k] = max (f[k - 1] , 0) + a[k]
        int n = nums.size();
        int f;
        int res = INT_MIN;
        f = nums[0];
        res = max(f , res);
        for(int i = 1 ; i < n ; i++){

            f = max(f , 0) + nums[i];
            //cout << f << " "; // 这样迭代出来的f表示前k个数字中的最大子数组和，
                                //但是答案需要最大的一个，所以要定义一个res保存最大的
            res = max(f , res);

        }

        //sort(f , f + n, [](int a,int b){return a < b ;} );
        return res;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla