Simple Java solution with O(n) time complexity and 4 line code


  • 0
    U
    We set the max and currMax to the first number in the array. Then start the loop from index 1 to the length of the array. Now in currMax, we decide that we should include the value of the current index of the array or not. And assign the max to the maximum of max till now or currMax.
    
    Time complexity: O(n), as we iterate till the length of the array once.
    Space complexity: O(1), as we are using space for max and currMax only which is a constant number.
    
    public int maxSubArray(int[] nums) {
            int max=nums[0], currMax=nums[0];
           
            for(int i=1;i<nums.length;i++){
                currMax= Math.max(nums[i], nums[i]+currMax);
                max=Math.max(max, currMax);
            }
            return max;
        }
    
    

Log in to reply
 

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