C++ O(N) Solution


  • 1
    P

    This problem is quite simple, actually question specifically asked about continous maximum sub array sum but you had to take atleast one element in it.

    First we would take a min value say -10000000000 and would comapre with each element, if it greater than this value we would replace min value by the element.

    We had taken a flag value and will set it to 1 when we encounter positive value. In this case we would add the element value in sum and would compare with our min value, if the sum value is greater than we will replace the min value.

    Now if the flag is set then we add element value in the sum and would compare first that it is greater than 0 and if it is then we would compare with min value and if it is also greater than it, we will replace the min value with sum. If the sum value is not greater than 0 then we will reset the flag and also set sum=0

    public:
        int maxSubArray(vector<int>& v1) {
            long long int arr_min = -10000000000, sum=0, flag=0;
            for(int i=0;i<v1.size();i++){
                if(v1[i]>arr_min)
                    arr_min=v1[i];
                if(flag==1){
                    if(sum+v1[i]>0){
                        sum=sum+v1[i];
                        if(sum > arr_min)
                            arr_min=sum;
                    }
                    else {
                        flag=0;
                        sum=0;
                    }
                }
                if(v1[i]>0 && flag==0){
                    flag=1;
                    sum=sum+v1[i];
                    if(sum>arr_min)
                        arr_min=sum;
                }
            }
            return arr_min;
        }
    };~~~
    
    Time complexity 0(N)
    Space complexity 0(1) (3 variable)

Log in to reply
 

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