DP Solution

  • 0

    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];
                dp[low][high] = Math.max(Math.max(maxSubArray(nums,dp,sum-nums[low],low+1,high),
            return dp[low][high];

Log in to reply

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