Java solution O(n) using : Kadane's algorithm


  • 1
    M

    Basically, using the Kadane's algorithm for maximum subarray : https://en.wikipedia.org/wiki/Maximum_subarray_problem.

    Time complexity O(n)
    Space complexity O(1)
    Status: Accepted
    Runtime: 16 ms

        public int maxSubArray(int[] nums) {
            
            int maxEndingHere = nums[0];
            int maxSoFar = nums[0];
            
            for (int i = 1; i < nums.length; i++) {
                int x = nums[i];
                maxEndingHere = Math.max(x, maxEndingHere + x);
                maxSoFar = Math.max(maxSoFar, maxEndingHere);
            }
            
            return maxSoFar;
            
        }
    

Log in to reply
 

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