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

  • 1

    Basically, using the Kadane's algorithm for maximum subarray :

    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.