Java solution -- O(n) dynamic programming


  • 0
    P
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int[] dp = new int[nums.length+1];
        
        for(int i=1; i<=nums.length; i++) {
            dp[i] = Math.max(nums[i-1], nums[i-1]+dp[i-1]); 
            //// dp[] store the value of max subarray which much include the ith element;
    
            max = Math.max(max, dp[i]);
            //// max is the real max subarray value;
        }
        return max;
    }

  • 0
    L

    DP solution with less space

    public int maxSubArray(int[] nums) {
        int max = nums[0];
        
        for(int i=1; i<nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i]+nums[i-1]); 
            //// dp[] store the value of max subarray which much include the ith element;
    
            max = Math.max(max, nums[i]);
            //// max is the real max subarray value;
        }
        return max;
    }

Log in to reply
 

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