DP Solution


  • 0
    T

    DP solution but inefficient...I guess with O(n^2) running and space complexity.

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

Log in to reply
 

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