class Solution { public int function(int[] nums , int x , int y){ //making dp int n = nums.length; int[] dp1 = new int[n]; //dp for MSA of x size int[] dp2 = new int[n]; //dp for MSA of y size int sum1 = 0 , sum2 = 0; for(int i = 0 , j = n-1 ; i < n ; i++ , j--){ int val = nums[i]; //if ith index is smaller than x store sum only if(i < x){ sum1 += val; dp1[i] = sum1; } //else check which is larger previous MSAx or sum including current //element else{ sum1 += nums[i] - nums[i-x]; dp1[i] = Math.max(dp1[i-1] ,sum1); } int val2 = nums[j]; //we fill 2nd array right to left if(j + y >= n){ sum2 += val2; dp2[j] = sum2; } //else check which is larger previous MSAy or sum including current //element else{ sum2 += nums[j] - nums[j+y]; dp2[j] = Math.max(dp2[j+1] , sum2); } } int ans = 0; //assuming x size MSA to be first and y size MSA to be 2nd for(int i = x-1 ; i < n-y ; i++) ans = Math.max(ans , dp1[i] + dp2[i+1]); return ans; } public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) { /* Q53 dp playlist ,we use kadane's algo to find MSA for x size and y size respectively for every element and then take max(MSAx + MSAy)for all indexes we fill 2nd dp right to left and 1st dp left to right similiarly we do the same this time assuming y size has occured first and then x size has occured and do the same finally we return max value of the two values obtained */ //assuming firstlen exists 1st and secondlen exists 2nd int ans1 = function(nums , firstLen , secondLen); //assuming firstlen exists 2nd and secondlen exists 1st int ans2 = function(nums , secondLen , firstLen); return Math.max(ans1 , ans2); } }