Q59 Temple Offerings | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            int N = Integer.parseInt(in.readLine());
            String a[] = in.readLine().trim().split("\\s+");
            int arr[] = new int[N];
            for(int i = 0; i < N;i++)
                arr[i] = Integer.parseInt(a[i]);
            
            Solution ob = new Solution();
            System.out.println(ob.offerings(N, arr));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution{
    int offerings(int n, int arr[]){
        /* Q59 of dp playlist , we traverse from left to right the temple and assign
        prev + 1 if we encounter a greater value else 1 , we do the same thing from right
        to left .
        
        we do this method inorder to get correct estimation of the no.downhill .for eg
        if uphill is 1 2 3 4 and then downhilll will be 3 2 1 0 -1 -2 -3 but we cant 
        give negative offering therefore we traverse from left to right also to get
        correct estimation of by taking max of (left ,right)
        */
        int left[] = new int[n] , right[] = new int[n];
        
        //left to right traverse
        left[0] = 1;
        for(int i = 1 ; i < n ;i++){
            
            //if we encounter greater temple we offer prev+1 offering
            if(arr[i] > arr[i-1])
            left[i] = left[i-1] + 1;
            
            //else offering resets to 1
            else
            left[i] = 1;
        }
        
        //similiarly for right to left 
        right[n-1] = 1;
        for(int i = n-2 ; i >=0 ; i--){
            
            if(arr[i] > arr[i+1])
            right[i] = right[i+1] +1;
            
            else
            right[i] = 1;
        }
        
        int ans = 0;
        
        //our answer will be correct estimation of temples offering which we will get 
        //by taking max of left and right for each temple
        for(int i = 0 ;i < n ; i++)
        ans += Math.max(left[i],right[i]);
        
        return ans;
    }
}