C++ O(N) codes less than 20 lines


  • 0
    W

    I want to post an intuitive and concise solution to this problem.
    Let's think like humans. We are finding the max sub array. It's either the current element or the sum of previous continual sum. The key point is when the continual sum is interrupted. It's just when the continual sum is less than ZERO!

    int maxSubArray(vector<int>& nums) { 
            int ans = nums[0];
            bool continual = ans > 0;
            int continual_sum = ans;
            for (size_t i = 1; i < nums.size(); ++i) { 
                if (continual) { 
                    continual_sum += nums[i];
                } else {
                    continual_sum = nums[i];
                }   
                if (continual_sum > ans) {
                    ans = continual_sum;
                }   
                continual = continual_sum >= 0;
            }       
            return ans;
    }       
    

Log in to reply
 

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