头像

张小白




离线:3小时前



张小白
4小时前

欢迎访问LeetCode题解合集

题目描述

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

题解:

题目已经保证区间没有重叠,且左端点从小到大排序,那么就非常容易了,设新插入的区间左右端点为 se,从左往右遍历每个区间:

  • seg[i][0] > e,说明没有交集,且此时找到了新插入区间的位置,将 {s, e} 保存到结果中,同时将 seg[i] 保存到结果中
  • seg[i][1] < s,说明没有交集,将 seg[i] 保存到结果中
  • 否则的话,说明有交集,因为 i 后面的区间也可能会继续与 {s, e} 产生交集,所以更新 s = min( s, seg[i][0] ), e = max( e, seg[i][1])
  • 如果遍历完所有区间,都没有找到 {s, e} 的插入位置,则把 {s, e} 插入到结果末尾

时间复杂度:$O(n)$

额外空间复杂度:$O(n)$

写法一(优雅):

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if ( !n || newInterval[1] < intervals[0][0] ) {
            intervals.insert( intervals.begin(), move(newInterval) );
            return intervals;
        }
        if ( newInterval[0] > intervals.back()[1] ) {
            intervals.push_back( move(newInterval) );
            return intervals;
        }
        vector<vector<int>> ret;
        int s = newInterval[0], e = newInterval[1];
        bool flag = false;
        for ( int i = 0; i < n; ++i ) {
            if ( intervals[i][1] < s ) {
                ret.push_back( move(intervals[i]) );
            } else if ( intervals[i][0] > e ) {
                if ( !flag ) {
                    ret.push_back( {s, e} );
                    flag = true;
                }
                ret.push_back( move(intervals[i]) );
            } else {
                s = min( s, intervals[i][0] );
                e = max( e, intervals[i][1] );
            }
        }
        if ( !flag ) ret.push_back({s, e});
        return ret;
    }
};
/*
时间:16ms,击败:99.36%
内存:16.6MB,击败:99.15%
*/

写法二(粗暴):

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if ( !n || newInterval[1] < intervals[0][0] ) {
            intervals.insert( intervals.begin(), move(newInterval) );
            return intervals;
        }
        if ( newInterval[0] > intervals.back()[1] ) {
            intervals.push_back( move(newInterval) );
            return intervals;
        }
        vector<vector<int>> ret;
        int s = newInterval[0], e = newInterval[1];
        int k = 0;
        while ( k < n && intervals[k][1] < s ) ret.push_back( move(intervals[k++]) );
        if ( k < n ) {
            s = min( s, intervals[k][0] );
            while ( k < n && intervals[k][0] <= e ) e = max( e, intervals[k++][1] );
        }
        ret.push_back({s, e});
        while ( k < n ) ret.push_back( move(intervals[k++]) );
        return ret;
    }
};
/*
时间:12ms,击败:99.84%
内存:16.5MB,击败:99.44%
*/


活动打卡代码 LeetCode 57. 插入区间

张小白
4小时前

写法一(优雅)

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if ( !n || newInterval[1] < intervals[0][0] ) {
            intervals.insert( intervals.begin(), move(newInterval) );
            return intervals;
        }
        if ( newInterval[0] > intervals.back()[1] ) {
            intervals.push_back( move(newInterval) );
            return intervals;
        }
        vector<vector<int>> ret;
        int s = newInterval[0], e = newInterval[1];
        bool flag = false;
        for ( int i = 0; i < n; ++i ) {
            if ( intervals[i][1] < s ) {
                ret.push_back( move(intervals[i]) );
            } else if ( intervals[i][0] > e ) {
                if ( !flag ) {
                    ret.push_back( {s, e} );
                    flag = true;
                }
                ret.push_back( move(intervals[i]) );
            } else {
                s = min( s, intervals[i][0] );
                e = max( e, intervals[i][1] );
            }
        }
        if ( !flag ) ret.push_back({s, e});
        return ret;
    }
};
/*
时间:16ms,击败:99.36%
内存:16.6MB,击败:99.15%
*/

写法二(粗暴)

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if ( !n || newInterval[1] < intervals[0][0] ) {
            intervals.insert( intervals.begin(), move(newInterval) );
            return intervals;
        }
        if ( newInterval[0] > intervals.back()[1] ) {
            intervals.push_back( move(newInterval) );
            return intervals;
        }
        vector<vector<int>> ret;
        int s = newInterval[0], e = newInterval[1];
        int k = 0;
        while ( k < n && intervals[k][1] < s ) ret.push_back( move(intervals[k++]) );
        if ( k < n ) {
            s = min( s, intervals[k][0] );
            while ( k < n && intervals[k][0] <= e ) e = max( e, intervals[k++][1] );
        }
        ret.push_back({s, e});
        while ( k < n ) ret.push_back( move(intervals[k++]) );
        return ret;
    }
};
/*
时间:12ms,击败:99.84%
内存:16.5MB,击败:99.44%
*/



张小白
6小时前

欢迎访问LeetCode题解合集

题目描述

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

  • $intervals[i][0] \le intervals[i][1]$

题解:

把区间按照 左端点从小到大 排序,左端点相同的话,右端点从大到小排序。

这样排序可以保证能够合并的区间是相邻的。

从前往后遍历数组,使用两个指针 se 分别记录 i 前面一个区间的左右端点:

  • seg[i][0] <= e ,说明当前区间和前面的区间有交集,合并它们, 也就是更新 e = max( e, seg[i][]1 )
  • seg[i][0] > e ,说明当前区间和前面的区间没有交集,需要把前面的区间保存到结果中,重新设置 s = seg[i][0], e = seg[i][1]

  • 遍历完数组后,把最后的 se 表示的区间保存到数组中

时间复杂度:$O(nlongn)$

额外空间复杂度:$O(n)$

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if ( n < 2 ) return intervals;
        sort( intervals.begin(), intervals.end() );
        vector<vector<int>> ret;
        int s = intervals[0][0], e = intervals[0][1];
        for ( int i = 1; i < n; ++i ) {
            if ( intervals[i][0] <= e ) {
                e = max( e, intervals[i][1] );
            } else {
                ret.push_back({s, e});
                s = intervals[i][0];
                e = intervals[i][1];
            }
        }
        ret.push_back({s, e});
        return ret;
    }
};
/*
时间:12ms,击败:99.93%
内存:13.8MB,击败:94.50%
*/


活动打卡代码 LeetCode 56. 合并区间

张小白
6小时前
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if ( n < 2 ) return intervals;
        sort( intervals.begin(), intervals.end() );
        vector<vector<int>> ret;
        int s = intervals[0][0], e = intervals[0][1];
        for ( int i = 1; i < n; ++i ) {
            if ( intervals[i][0] <= e ) {
                e = max( e, intervals[i][1] );
            } else {
                ret.push_back({s, e});
                s = intervals[i][0];
                e = intervals[i][1];
            }
        }
        ret.push_back({s, e});
        return ret;
    }
};
/*
时间:12ms,击败:99.93%
内存:13.8MB,击败:94.50%
*/


活动打卡代码 AcWing 420. 火星人

张小白
7小时前
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10010;

int a[N];
int n, m;

int main(void) {
    scanf("%d%d", &n, &m);
    for ( int i = 0; i < n; ++i )
        scanf("%d", a + i);
    while ( m-- ) {
        int k = n - 1;
        while ( k > 0 && a[k - 1] > a[k] ) --k;
        if ( --k < 0 ) break;
        int t = n - 1;
        while ( t > k && a[t] < a[k] ) --t;
        swap( a[t], a[k] );
        reverse( a + k + 1, a + n );
    }
    for ( int i = 0; i < n; ++i )
        printf("%d%c", a[i], " \n"[i == n - 1]);
    return 0;
}



张小白
23小时前

欢迎访问LeetCode题解合集

题目描述

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

题解:

法一:

动态规划。设 f[i] 表示能否到达 i 位置,那么转移方程就是:

f[i] = f[i] | f[j](0 <= j < i && j + nums[j] >= i)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n);
        f[0] = true;
        for ( int i = 1, j; i < n; ++i ) {
            for ( j = 0; j < i; ++j )
                if ( f[j] && j + nums[j] >= i ) {
                    f[i] = true;
                    break;
                }
            if ( j == i ) return false;
        }
        return f[n - 1];
    }
};

该版本时间复杂度为:$O(n^2)$,肯定过不了的。

可以发现,影响该版本的效率主要在第二重循环,每次都是从头开始查找第一个能到达 i 的位置,而我们可以使用一个变量 last 记录到达 i 的第一个位置,在 i+1 位置时, 0~last-1 位置不用遍历了,因为它们到不了 i ,那肯定也到不了 i+1 。所以,直接从 last 开始遍历,并且可以不使用额外数组记录状态。

时间复杂度:$O(n)$

额外空间复杂度:$O(1)$

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;
        for ( int i = 1; i < n; ++i ) {
            while ( last < i && i > last + nums[last] ) ++last;
            if ( last == i ) return false;
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.5MB,击败:95.53%
*/
法二:

贪心。

right 表示 0~i-1 这些位置都能到达,且它们中能跳到的最远的位置。那么对于位置 i 来说:

  • i > right ,说明无法到达 i 位置,那么肯定也无法到达 n-1 位置,直接返回 false
  • i <= right ,说明可以到达 i 位置,因为在位置 i 可能会跳到更远的位置,所以更新 right = max(right, i + nums[i])
  • right >= n - 1 ,说明已经能到达 n-1 位置了,直接返回 true

时间复杂度:$O(n)$

额外空间复杂度:$O(1)$

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int right = 0, n = nums.size();
        for ( int i = 0; i < n; ++i ) {
            if ( right < i ) return false;
            right = max( right, i + nums[i] );
            if ( right >= n - 1 ) return true;
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.4MB,击败:98.09%
*/
法三:

另外一种贪心。

问题换一个描述:我们在玩跳方格游戏,每次只能前进一个格子,消耗一个单位的能量值。每个格子上有一瓶 nums[i] 单位的能量药剂,可以选择捡或者不捡,任何时刻只能携带一瓶能量药剂,问能否到达最后一个格子。

我们可以使用 rest 记录当前还剩多少单位的能量,初始时在 0 位置,rest = nums[0] ,分情况讨论:

  • rest <= 0 ,说明无法跳到下一个位置,直接返回 false
  • 否则说明能跳到下一个位置,此时面临选择能量药剂的问题,策略是:自身剩下的和格子上的,哪个大选哪个,即 rest = max(rest - 1, nums[i])

时间复杂度:$O(n)$

额外空间复杂度:$O(1)$

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rest = nums[0];
        for ( int i = 1; i < n; ++i ) {
            if ( rest <= 0 ) return false;
            rest = max( rest - 1, nums[i] );
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.3MB,击败:98.66%
*/


活动打卡代码 LeetCode 55. 跳跃游戏

张小白
23小时前

动态规划(超时)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n);
        f[0] = true;
        for ( int i = 1, j; i < n; ++i ) {
            for ( j = 0; j < i; ++j )
                if ( f[j] && j + nums[j] >= i ) {
                    f[i] = true;
                    break;
                }
            if ( j == i ) return false;
        }
        return f[n - 1];
    }
};

动态规划优化

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;
        for ( int i = 1; i < n; ++i ) {
            while ( last < i && i > last + nums[last] ) ++last;
            if ( last == i ) return false;
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.5MB,击败:95.53%
*/

贪心(一)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int right = 0, n = nums.size();
        for ( int i = 0; i < n; ++i ) {
            if ( right < i ) return false;
            right = max( right, i + nums[i] );
            if ( right >= n - 1 ) return true;
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.4MB,击败:98.09%
*/

贪心(二)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rest = nums[0];
        for ( int i = 1; i < n; ++i ) {
            if ( rest <= 0 ) return false;
            rest = max( rest - 1, nums[i] );
        }
        return true;
    }
};
/*
时间:8ms,击败:98.55%
内存:12.3MB,击败:98.66%
*/



欢迎访问LeetCode题解集合

题目描述

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

题解:

模拟。

但写法还是有点技巧的。首先移动的方向是 右 下 左 上 ,不停的依次循环这 4 个方向,直到遍历完所有元素。

那么我们就要按照上述四个方向走,模拟下标的变化。

有两种写法:

第一种是手动模拟这个过程,稍微麻烦点,但好理解:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, k = 0;
        while ( k < m * n ) {
            while ( sy < m && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy++] = FLAG;
            }
            ++sx, --sy;
            while ( sx < n && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx++][sy] = FLAG;
            }
            --sx, --sy;
            while ( sy >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy--] = FLAG;
            }
            --sx, ++sy;
            while ( sx >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx--][sy] = FLAG;
            }
            ++sx, ++sy;
        }
        return ret;
    }
};
/*
时间:0ms,击败:100.00%
内存:6.6MB,击败:95.50%
*/

第二种是使用一个方向变量 d 控制移动方向,使用两个数组记录对应方向上坐标的偏移量,只要保证 d 的改变和坐标偏移量一一对应即可。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        vector<int> dx{ 0, 1, 0, -1 };
        vector<int> dy{ 1, 0, -1, 0 };
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, d = 0, tx, ty;
        for ( int i = 0; i < n * m; ++i ) {
            ret[i] = matrix[sx][sy];
            matrix[sx][sy] = FLAG;
            tx = sx + dx[d];
            ty = sy + dy[d];
            if ( tx < 0 || tx >= n || ty < 0 || ty >= m || matrix[tx][ty] == FLAG ) {
                d = (d + 1) % 4;
                tx = sx + dx[d];
                ty = sy + dy[d];
            }
            sx = tx;
            sy = ty;
        }
        return ret;
    }
};
/*
时间:0ms,击败:100.00%
内存:6.6MB,击败:98.10%
*/


活动打卡代码 LeetCode 54. 螺旋矩阵

写法一

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, k = 0;
        while ( k < m * n ) {
            while ( sy < m && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy++] = FLAG;
            }
            ++sx, --sy;
            while ( sx < n && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx++][sy] = FLAG;
            }
            --sx, --sy;
            while ( sy >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy--] = FLAG;
            }
            --sx, ++sy;
            while ( sx >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx--][sy] = FLAG;
            }
            ++sx, ++sy;
        }
        return ret;
    }
};
/*
时间:0ms,击败:100.00%
内存:6.6MB,击败:95.50%
*/

写法二

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        vector<int> dx{ 0, 1, 0, -1 };
        vector<int> dy{ 1, 0, -1, 0 };
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, d = 0, tx, ty;
        for ( int i = 0; i < n * m; ++i ) {
            ret[i] = matrix[sx][sy];
            matrix[sx][sy] = FLAG;
            tx = sx + dx[d];
            ty = sy + dy[d];
            if ( tx < 0 || tx >= n || ty < 0 || ty >= m || matrix[tx][ty] == FLAG ) {
                d = (d + 1) % 4;
                tx = sx + dx[d];
                ty = sy + dy[d];
            }
            sx = tx;
            sy = ty;
        }
        return ret;
    }
};
/*
时间:0ms,击败:100.00%
内存:6.6MB,击败:98.10%
*/



欢迎访问LeetCode题解合集

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。


题解:

法一:

三重循环,第一重循环枚举起点,第二重循环枚举终点,第三重循环求起点和终点之间的和。

时间复杂度:$O(n^3)$

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int max_sum = INT_MIN, sum;
        for ( int i = 0; i < n; ++i ) {
            for ( int j = i; j < n; ++j ) {
                sum = 0;
                for ( int k = i; k <= j; ++k )
                    sum += nums[k];
                if ( sum > max_sum ) max_sum = sum;
            }
        }
        return max_sum;
    }
};

这个版本代码超时。可以优化掉第三维,求区间和可以利用前缀和搞定。

时间复杂度:$O(n^2)$

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        for ( int i = 1; i <= n; ++i )
            f[i] = f[i - 1] + nums[i - 1];
        int max_sum = INT_MIN, sum;
        for ( int i = 1; i <= n; ++i ) {
            for ( int j = i; j <= n; ++j ) {
                sum = f[j] - f[i - 1];
                if ( sum > max_sum ) max_sum = sum;
            }
        }
        return max_sum;
    }
};
/*
时间:1340ms,击败:5.08%
内存:12.9MB,击败:90.30%
*/

勉强能过这题。但是时间复杂度还是有点爆炸。。。

当然,也可以在第二重循环直接累加求和,不用开辟额外的空间。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int max_sum = INT_MIN, sum;
        for ( int i = 0; i < n; ++i ) {
            sum = 0;
            for ( int j = i; j < n; ++j ) {
                sum += nums[j];
                if ( sum > max_sum ) max_sum = sum;
            }
        }
        return max_sum;
    }
};
/*
时间:736ms,击败:5.08%
内存:12.9MB,击败:90.45%
*/
法二:

动态规划。f[i] 表示以 nums[i] 结尾的连续子数组的最大和。那么转移方程就是:$f[i] = max(nums[i], f[i - 1] + nums[i])$

时间复杂度:$O(n)$

额外空间复杂度:$O(n)$

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        int max_sum = nums[0];
        for ( int i = 1; i < n; ++i ) {
            f[i] = max( nums[i], f[i - 1] + nums[i] );
            if ( f[i] > max_sum ) max_sum = f[i];
        }
        return max_sum;
    }
};
/*
时间:8ms,击败:95.00%
内存:13MB,击败:88.66%
*/
法三:

分治。将一个区间 [l, r] 划分成 [l, m][m + 1, r] 两部分,那么最大子段和可能存在三种情况:

  • 左边区间
  • 右边区间
  • 横跨左右两个区间

时间复杂度:$O(nlogn)$

class Solution {
public:
    int merge( int l, int r, vector<int>& nums ) {
        if ( l == r ) return nums[l];
        int m = (l + r) >> 1;
        int maxLeftSum = merge(l, m, nums);
        int maxRighSum = merge(m + 1, r, nums);
        int maxLeftBorderSum = INT_MIN;
        int ans = 0;
        for ( int i = m; i >= l; --i ) {
            ans += nums[i];
            if( ans > maxLeftBorderSum )
                maxLeftBorderSum = ans;
        }
        int maxRighBorderSum = INT_MIN;
        ans = 0;
        for ( int i = m + 1; i <= r; ++i ) {
            ans += nums[i];
            if ( ans > maxRighBorderSum )
                maxRighBorderSum = ans;
        }
        return max( {maxLeftSum, maxRighSum, maxLeftBorderSum + maxRighBorderSum} );
    }
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return merge(0, n - 1, nums);
    }
};
/*
时间:12ms,击败:81.33%
内存:12.7MB,击败:99.38%
*/
法四:

贪心。

方法二 中,动态规划转移方程为:$f[i] = max(nums[i], f[i - 1] + nums[i])$ ,可以发现,如果 f[i - 1] < 0 ,也就是以 nums[i - 1] 结尾的最大子段和是 小于0 的,那么 nums[i] 肯定不能接在 nums[i - 1] 后面(不然就是接盘侠),也就是说,需要从 i 位置从头开始求最大子段和了,前面的可以直接扔掉,所以可以贪心求解。

时间复杂度:$O(n)$

额外空间复杂度:$O(1)$

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int max_sum = INT_MIN, sum = 0;
        for ( auto& it : nums ) {
            if ( sum >= 0 ) sum += it;
            else sum = it;
            max_sum = max( max_sum, sum );
        }
        return max_sum;
    }
};
/*
时间:4ms,击败:99.46%
内存:12.8MB,击败:96.01%
*/