Given an array arr[]. The task is to find the maximum score that can be achieved from arr[] for i=[1, N-2]. The conditions for scoring are given below.
- If arr[0…j] < arr[i] < arr[i+1…N-1], then score = 2.
- If arr[i-1] < arr[i] < arr[i+1] and previous condition is not satisfied, then score = 1.
- If none of the conditions holds, then score = 0.
Examples:
Input: arr[] = {1, 2, 3}
Output: 2
Explanation: The score of arr[1] equals 2, which is maximum possible.Input: arr[] = {2, 4, 6, 4}
Output: 1
Explanation: For each index i in the range 1 <= i <= 2:
The score of nums[1] equals 1.
The score of nums[2] equals 0.
Hence 1 is the maximum possible score.
Approach: This problem can be solved by using Prefix Max and Suffix Min. Follow the steps below to solve the given problem.
- For an element score to be 2, it should be greater than every element on its left and smaller than every element on its right.
- So Precompute to find prefix max and suffix min for each array element.
- Now check for each array arr[] element at i:
- If it is greater than prefix max at i-1, and smaller than suffix min at i+1, the score will be 2.
- else if it is greater than arr[i-1] and smaller than arr[i+1], score will be 1.
- else score will be 0.
- Sum up all the scores and return that as the final answer.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum scoreint maxScore(vector<int>& nums){ // Size of array int n = nums.size(), i; int ans = 0; // Prefix max vector<int> pre(n, 0); // Suffix min vector<int> suf(n, 0); pre[0] = nums[0]; for (i = 1; i < n; i++) pre[i] = max(pre[i - 1], nums[i]); suf[n - 1] = nums[n - 1]; for (i = n - 2; i >= 0; i--) suf[i] = min(suf[i + 1], nums[i]); for (i = 1; i < n - 1; i++) { if (nums[i] > pre[i - 1] && nums[i] < suf[i + 1]) ans += 2; else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) ans += 1; } return ans;}// Driver Codeint main(){ int N = 3; vector<int> arr = { 1, 2, 3 }; // Function Call cout << maxScore(arr); return 0;} |
Java
// Java program for above approachimport java.util.*;public class GFG{ // Function to find maximum score static int maxScore(ArrayList<Integer> nums) { // Size of array int n = nums.size(), i = 0; int ans = 0; // Prefix max int[] pre = new int[n]; // Suffix min int[] suf = new int[n]; pre[0] = (int)nums.get(0); for (i = 1; i < n; i++) pre[i] = Math.max(pre[i - 1], (int)nums.get(i)); suf[n - 1] = (int)nums.get(n - 1); for (i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], (int)nums.get(i)); for (i = 1; i < n - 1; i++) { if ((int)nums.get(i) > pre[i - 1] && (int)nums.get(i) < suf[i + 1]) ans += 2; else if ((int)nums.get(i) > (int)nums.get(i - 1) && (int)nums.get(i) < (int)nums.get(i + 1)) ans += 1; } return ans; } // Driver Code public static void main(String args[]) { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(1); arr.add(2); arr.add(3); // Function Call System.out.println(maxScore(arr)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# python program for above approach# Function to find maximum scoredef maxScore(nums): # Size of array n = len(nums) ans = 0 # Prefix max pre = [0 for _ in range(n)] # Suffix min suf = [0 for _ in range(n)] pre[0] = nums[0] for i in range(1, n): pre[i] = max(pre[i - 1], nums[i]) suf[n - 1] = nums[n - 1] for i in range(n-2, -1, -1): suf[i] = min(suf[i + 1], nums[i]) for i in range(1, n-1): if (nums[i] > pre[i - 1] and nums[i] < suf[i + 1]): ans += 2 elif (nums[i] > nums[i - 1] and nums[i] < nums[i + 1]): ans += 1 return ans# Driver Codeif __name__ == "__main__": N = 3 arr = [1, 2, 3] # Function Call print(maxScore(arr))# This code is contributed by rakeshsahni |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG{ // Function to find maximum score static int maxScore(List<int> nums) { // Size of array int n = nums.Count, i = 0; int ans = 0; // Prefix max int[] pre = new int[n]; // Suffix min int[] suf = new int[n]; pre[0] = nums[0]; for (i = 1; i < n; i++) pre[i] = Math.Max(pre[i - 1], nums[i]); suf[n - 1] = nums[n - 1]; for (i = n - 2; i >= 0; i--) suf[i] = Math.Min(suf[i + 1], nums[i]); for (i = 1; i < n - 1; i++) { if (nums[i] > pre[i - 1] && nums[i] < suf[i + 1]) ans += 2; else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) ans += 1; } return ans; } // Driver Code public static void Main() { List<int> arr = new List<int>() { 1, 2, 3 }; // Function Call Console.WriteLine(maxScore(arr)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find maximum score function maxScore(nums) { // Size of array let n = nums.length, i; let ans = 0; // Prefix max let pre = new Array(n).fill(0) // Suffix min let suf = new Array(n).fill(0); pre[0] = nums[0]; for (i = 1; i < n; i++) pre[i] = Math.max(pre[i - 1], nums[i]); suf[n - 1] = nums[n - 1]; for (i = n - 2; i >= 0; i--) suf[i] = Math.min(suf[i + 1], nums[i]); for (i = 1; i < n - 1; i++) { if (nums[i] > pre[i - 1] && nums[i] < suf[i + 1]) ans += 2; else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) ans += 1; } return ans; } // Driver Code let N = 3; let arr = [1, 2, 3]; // Function Call document.write(maxScore(arr));// This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!