C++ Simple Fast O(N) Solution


  • 0
    M

    We can observe that for each i best solution (maximum sum) for segment ending at i will be sum([0, i]) - min(sum([0, j])) for j < i, also sum([j, i]) = sum([0, i]) - sum([0, j - 1]), i.e. to find biggest sum of segment ending at i we need to subtract minimal (sum-wise) segment [0, j], j < i. Then we need just to compute maximum out of all i-ending segments.

    Time Complexity: O(N)
    Space Complexity: O(1)

    #include <algorithm>
    using namespace std;
    
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if (nums.empty()) return 0;
            int begin_sum = 0, min_begin_sum = 0, max_interval_sum = nums[0];
            for (int i = 0; i < nums.size(); ++i) {
                begin_sum += nums[i];
                max_interval_sum = max(max_interval_sum, begin_sum - min_begin_sum);
                min_begin_sum = min(min_begin_sum, begin_sum);
            }
            return max_interval_sum;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.