Q54 Maximum Sum of 3 Non-Overlapping Subarrays - LeetCode 689

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;
    }
}