class Solution { public int maxCoins(int[] nums) { //this is a question of matrix chain multiplication dp playlist vid23 //adding an extra 1 in the end of the array int n = nums.length; int dp[][] = new int[n][n]; for(int gap = 0; gap < n ; gap++){ for(int i = 0 , j = gap ; j < n ; i++ , j++){ int max = Integer.MIN_VALUE; for(int k = i ; k <= j ;k++){ int left = k==i ? 0: dp[i][k-1] ; int right = k==j ? 0: dp[k+1][j] ; //cost = nums[i-1] * nums[k] * nums[j+1] //handling for i==0 and j == n-1 int cost = nums[k]; cost *= i > 0 ? nums[i-1] : 1; cost *= j != n-1 ? nums[j+1] :1; max = Math.max(max , left + right + cost); } dp[i][j] = max; } } return dp[0][n-1]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter