连续子数组的最大和(二)

C++ 解法, 执行用时: 12ms, 内存消耗: 2688KB, 提交时间: 2021-12-27

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        vector<int>::iterator l = array.begin(), r = l + 1;
        vector<int>::iterator max_l = l, max_r = r;
        int sum = array[0], max = sum;
        for(int i=1; i<array.size(); i++) {
            if(__builtin_expect(sum < 0, 0)) {
                sum = 0;
                l = array.begin() + i;
                r = l;
            }
            sum += array[i];
            r++;
            if(sum >= max) {
                max = sum;
                max_l = l;
                max_r = r;
            }
        }
        return {max_l, max_r};
    }
};

C++ 解法, 执行用时: 15ms, 内存消耗: 2688KB, 提交时间: 2022-03-08

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        // 空数组直接返回
        if (array.size() == 0)    return array;
        // 初始化动态规划状态
        int dp = array[0], maxSub = array[0];
        // 左右指针
        int left = 0, right = 0;
        // 最终左右指针
        int leftLongest = 0, rightLongest = 0;
        
        // 遍历数组
        for (int idx = 1; idx < array.size(); idx++)
        {
            if (array[idx] > dp + array[idx])
            {
                dp = array[idx];
                left = idx;
                right = idx;
            }
            else
            {
                dp += array[idx];
                right++;
            }
            
            // 更新最大值与最大区间
            if (dp >= maxSub)
            {
                maxSub = dp;
                rightLongest = right;
                leftLongest = left;
            }
        }
        
        return {array.begin() + leftLongest, array.begin() + rightLongest + 1};
    }
};

C++ 解法, 执行用时: 15ms, 内存消耗: 2688KB, 提交时间: 2021-12-20

const static auto sync_off = []{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if(array.empty()) return {};
        vector<int> ve_o;
        long pre = 0, max_sum = array[0];
        int max_pos = 0, tmp_pos = 0;
        int max_len = 0, tmp_len = 0;
        for(int i = 0; i < array.size(); ++i){
            if(pre >= 0){
                pre += array[i];
                ++tmp_len;
            }
            else{
                pre = array[i];
                tmp_len = 1;
                tmp_pos = i;
            }
            if(pre == max_sum){
                if(tmp_len > max_len){
                    max_len = tmp_len;
                    max_pos = tmp_pos;
                }
            }
            else if(pre > max_sum){
                max_len = tmp_len;
                max_sum = pre;
                max_pos = tmp_pos;
            }
        }
        ve_o.assign(array.begin() + max_pos, array.begin() + max_pos + max_len);
        return ve_o;
    }
};

C++ 解法, 执行用时: 15ms, 内存消耗: 2700KB, 提交时间: 2022-05-08

static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}
();
class Solution {
  public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        vector<int>::iterator l = array.begin(), r = l + 1;
        vector<int>::iterator max_l = l, max_r = r;
        int sum = array[0], max = sum;
        for (int i = 1; i < array.size(); i++) {
            if (__builtin_expect(sum < 0, 0)) {
                sum = 0;
                l = array.begin() + i;
                r = l;
            }
            sum += array[i];
            r++;
            if (sum >= max) {
                max = sum;
                max_l = l;
                max_r = r;
            }
        }
        return {max_l, max_r};
    }
};

C++ 解法, 执行用时: 15ms, 内存消耗: 2928KB, 提交时间: 2022-06-01

const static auto sync_off = []{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        vector<int> res;
        int n = array.size();
        vector<int> dp(n, 0);
        dp[0] = array[0];
        int max_sum = dp[0];
        int left = 0, right = 0;
        int res_l = 0, res_r = 0;
        for (int i = 1; i < n; i++) {
            right++;
            dp[i] = max(dp[i - 1] + array[i], array[i]);
            if (dp[i - 1] + array[i] < array[i]) {
                left = right;
            }
            if (max_sum < dp[i] || max_sum == dp[i] && (right - left) > (res_r - res_r)) {
                max_sum = dp[i];
                res_l = left;
                res_r = right;
            }
        }
        for (int i = res_l; i <= res_r; i++) {
            res.emplace_back(array[i]);
        }
        return res;
    }
};

详情