Kadane's Algorithm. O(N) time and O(1) space. Way to handle all the corner case when all numbers are negative.( I know there is a better way to express my idea in terms of code so I'll appreciate if anyone does that.)


  • 0
    A
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int max=nums[0];
            bool flag=false;
            for(int i=0;i<nums.size();i++){
                if(nums[i] > max)
                    max=nums[i];
                if(nums[i] >= 0){
                    flag=true;
                    break;
                }
            }
            if(!flag)
                return max;
            
            int sum=0, ans=0;
            for(int i=0;i<nums.size();i++){
                sum += nums[i];
                if( sum  < 0 ){
                    sum=0;
                }
                else{
                    ans = ( ans > sum ) ? ans : sum; 
                }
            }
            return ans;
        }
    };
    

    I'll start with the Kadane's algorithm first for which it is required that we have at least one number greater than or equal to zero. We maintain two variables "sum" and "ans". So we iterate through the array and keep adding to the sum. If after the addition the sum becomes negative we set it back to 0 else we check whether the current value of sum is greater than the ans(max sum subarray) we got uptill now.

    This is you rightly thought so won't work if all numbers are negative. In which case the maximum sum subarray will be the largest number amongst all the negative numbers and hence before applying Kadane's algorithm we check if there is at least one number greater than or equal to 0. If no then we return the maximum found amongst the negative numbers. Both the first and the second step take O(N) time and hence the overall time complexity of the solution is O(N).


Log in to reply
 

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