class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { /* Q54 of dp playlist */ //making 3 arrays left ,right and PSA int n = nums.length; int[] left = new int[n] , right = new int[n] , psa = new int[n]; //making prefix sum array for(int i = 0 ;i < n ;i++){ if(i==0) psa[i] = nums[i]; else psa[i] = psa[i-1] + nums[i]; } //now making left and right dp arrays int sum1 = 0 , sum2 = 0; for(int i = 0 , j = n-1 ; i < n ; i++ ,j--){ if(i < k){ sum1 += nums[i]; left[i] = sum1; } else{ sum1 += nums[i] - nums[i-k]; left[i] = Math.max(sum1 , left[i-1]); } if(j+k >= n){ sum2 += nums[j]; right[j] = sum2; } else{ sum2 += nums[j] - nums[j+k]; right[j] = Math.max(sum2 , right[j+1]); } } //now traversing the middle array and finding max combination of //left + middle + right and also finding the indexes of all 3 arrays int ans = Integer.MIN_VALUE; int li = -1 , mi = -1 , ri = -1; //left idx ,middle idx , right idx for(int i = k ; i <= n - 2*k ; i++){ int middle = psa[i + k -1] - psa[i-1]; int val = left[i-1] + right[i+k] + middle; if(val > ans){ ans = val; li = left[i-1] ; mi = i ; ri = right[i+k]; } } // System.out.println(li + " " + mi + " " + ri); /* now that we have the indexes of all 3 we can find lexiographically first index of all 3 subarray by storing the first value which comes for left ,right */ // for(int i = 0 ;i < n ; i++) // System.out.print(left[i] + " "); // System.out.println(); // for(int i = 0 ;i < n ; i++) // System.out.print(right[i] + " "); // System.out.println(); //finding lexiographically first index of left by comparing value of Li for(int i = k-1 ; i <= mi-1 ; i++){ if(psa[i] - (i-k < 0 ? 0 : psa[i-k])==li){ li = i-k+1; break; } } //finding lexiographically first index of right by comparing value of Ri for(int i = mi + (2 * k)-1 ; i < n ; i++){ if(psa[i] - psa[i-k] == ri){ ri = i-k+1; break; } } // System.out.println(li + " " + mi + " " + ri); int[] list = {li , mi , ri}; return list; } }
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