Java O(n) solution using DP


  • 3
    W

    Maintain an array max such that max[i] has the maximum sum if A[i] is the last element of that subarray.

    Recursive definition : max[i] = max { A[i], A[i] + max[i - 1] }

    Base case: max[0] = A[0]

    We can then use the bottom-up approach of Dynamic Programming instead of doing it recursively. Following is the code :-

    public class Solution {
        public int maxSubArray(int[] nums) {
            if(nums.length == 0)
                return 0;
            int maxIndex = 0;
            int[] max = new int[nums.length];
            max[0] = nums[0];
            for(int i = 1; i < nums.length; i++) {
                max[i] = Math.max(nums[i], nums[i] + max[i - 1]);
                if(max[i] > max[maxIndex])
                    maxIndex = i;
            }
            return max[maxIndex];
        }
    }

  • 0
    L

    How to do it recursively if we want to use top-down approach?


Log in to reply
 

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