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