Beats 100% users in Memory & Time | Tabulation | Dynamic Programming | JAVA | Memoization to Tabulat
Here I have attempted to convert Memoization code to tabulation as with Memoization we get TLE. MOD is used to handle large test cases.\n\nMemoization approach:
Here I have attempted to convert Memoization code to tabulation as with Memoization we get TLE. MOD is used to handle large test cases.\n\n**Memoization approach**: Solved using take and not take technique. If we take that index we add it and pass the call to i+2 when doing recursion. If we don not take simply call the function with i+1 index element. In the end, we set the answer as maximum of take and not take.\n\n**Tabulation approach** : To convert recursion to tabulation, base case is the last index.If nums size is 5 then dp[5] = Math.max(nums[5]+0, 0) this is because there are no more elements after last index.\nSimilarly second last index\'s take is handled by setting that value to 0 as second last index next value will be out of bounds.\n\n# Code\n```\nclass Solution {\n    private static final int MOD = 1000000007;\n\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        int sum = 0;\n        for(int[] q : queries){\n            nums[q[0]] = q[1];\n            sum = (sum + fun(nums))%MOD;\n        }\n        return sum;\n    }\n    \n    private int fun(int[] nums){\n        int n = nums.length;\n        int[]dp = new int[nums.length];\n\n        for(int i = n-1; i>=0; i--){\n            if(i == n-1){\n                dp[i] = Math.max(nums[i], 0);\n            }else{\n                int next = i+2>=n?0:dp[i+2]; \n                dp[i] = Math.max(nums[i]+next, dp[i+1]);\n            }\n        }\n        return dp[0];\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Java']