Given an array arr[] of N integers and Q queries. Each query consists of 3 integers L, R and K. You can move from index i to index i + 1 in a single step or stay in that particular index in a single step. You can move from L to R index in a maximum of K steps and print the summation of every number you were at in every step including the L-th number. The task is to maximize the summation in a maximum of K moves. If we cannot move from L to R in K steps then print “No”.
Examples:
Input: arr[] = {1, 3, 2, -4, -5}, q = {
{0, 2, 2},
{0, 2, 4},
{3, 4, 1},
{0, 4, 2}}
Output:
6
12
-9
No
For first query:
In first step move from 0th index to 1st index, hence 1 + 3 = 4
In second step move from 1st index to 2nd index, hence 4 + 2 = 6
For second query:
In first step move from 0th index to 1st index, hence 1 + 3 = 4
In second step stay at the 1st index, hence 4 + 3 = 7
In third step again stay at the 1st index, hence 7 + 3 = 10
In fourth step move from 1st index to 2nd index only, hence 10 + 2 = 12
A naive approach is to check first if L – R > K, if it is then we cannot move from L to R index in K steps. Iterate from L to R, get the sum of all elements between L and R. Then find the maximum element in the range L and R and the answer will be the sum of elements in the range and (K – (R – L)) * maximum. If the maximum is a negative number we exactly perform R – L moves else we perform the extra steps at the maximum number index in the range [L, R].
Time Complexity: O(R – L) per query.
An efficient approach is to use segment tree in the range [L, R] to find the maximum number and find the sum in the range using prefix sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to create the treevoid tree(int low, int high, int pos, int b[], int a[], int n){ // Leaf nodes if (low == high) { b[pos] = a[high]; return; } int mid = (high + low) / 2; // Left subtree tree(low, mid, 2 * pos + 1, b, a, n); // Right subtree tree(mid + 1, high, 2 * pos + 2, b, a, n); // Merge the maximum b[pos] = max(b[2 * pos + 1], b[2 * pos + 2]);}// Function that returns the maximum in range L and Rint rangemax(int s, int e, int low, int high, int pos, int b[], int a[], int n){ // Complete overlap if (low <= s && high >= e) return b[pos]; // Out of range completely if (e < low || s > high) return INT_MIN; int mid = (s + e) / 2; // Find maximum in left and right subtrees int left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n); int right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n); // Return the maximum of both return max(left, right);}// Function that solves a queryint solveQuery(int l, int r, int k, int n, int a[], int b[], int prefix[]){ // If there are ko if (r - l > k) return -1; // Find maximum in range L and R int maximum = rangemax(0, n - 1, l, r, 0, b, a, n); // If maximum is 0 if (maximum < 0) maximum = 0; // Find the prefix sum int rangesum = prefix[r]; // If not first element if (l > 0) rangesum -= prefix[l - 1]; // Get the answer int answer = rangesum + (k - (r - l)) * maximum; return answer;}// Function that solves the queriesvoid solveQueries(int n, int a[], int b[], int prefix[], int queries[][3], int q){ // Solve all the queries for (int i = 0; i < q; i++) { int ans = solveQuery(queries[i][0], queries[i][1], queries[i][2], n, a, b, prefix); if (ans != -1) cout << ans << endl; else cout << "No" << endl; }}// Function to find the prefix sumvoid findPrefixSum(int prefix[], int a[], int n){ prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; }}// Driver codeint main(){ int a[] = { 1, 3, 2, -4, -5 }; int n = sizeof(a) / sizeof(a[0]); // Array for segment tree int b[5 * n]; // Create segment tree tree(0, n - 1, 0, b, a, n); int prefix[n]; // Fill prefix sum array findPrefixSum(prefix, a, n); // Queries int queries[][3] = { { 0, 2, 2 }, { 0, 2, 4 }, { 3, 4, 1 }, { 0, 4, 2 } }; int q = sizeof(queries) / sizeof(queries[0]); solveQueries(n, a, b, prefix, queries, q); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to create the treestatic void tree(int low, int high, int pos, int b[], int a[], int n){ // Leaf nodes if (low == high) { b[pos] = a[high]; return; } int mid = (high + low) / 2; // Left subtree tree(low, mid, 2 * pos + 1, b, a, n); // Right subtree tree(mid + 1, high, 2 * pos + 2, b, a, n); // Merge the maximum b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);}// Function that returns the maximum in range L and Rstatic int rangemax(int s, int e, int low, int high, int pos, int b[], int a[], int n){ // Complete overlap if (low <= s && high >= e) return b[pos]; // Out of range completely if (e < low || s > high) return Integer.MIN_VALUE; int mid = (s + e) / 2; // Find maximum in left and right subtrees int left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n); int right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n); // Return the maximum of both return Math.max(left, right);}// Function that solves a querystatic int solveQuery(int l, int r, int k, int n, int a[], int b[], int prefix[]){ // If there are ko if (r - l > k) return -1; // Find maximum in range L and R int maximum = rangemax(0, n - 1, l, r, 0, b, a, n); // If maximum is 0 if (maximum < 0) maximum = 0; // Find the prefix sum int rangesum = prefix[r]; // If not first element if (l > 0) rangesum -= prefix[l - 1]; // Get the answer int answer = rangesum + (k - (r - l)) * maximum; return answer;}// Function that solves the queriesstatic void solveQueries(int n, int a[], int b[], int prefix[], int queries[][], int q){ // Solve all the queries for (int i = 0; i < q; i++) { int ans = solveQuery(queries[i][0], queries[i][1], queries[i][2], n, a, b, prefix); if (ans != -1) System.out.println(ans); else System.out.println("No" ); }}// Function to find the prefix sumstatic void findPrefixSum(int prefix[], int a[], int n){ prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; }}// Driver codepublic static void main(String[] args){ int a[] = { 1, 3, 2, -4, -5 }; int n = a.length; // Array for segment tree int b[] = new int[5 * n]; // Create segment tree tree(0, n - 1, 0, b, a, n); int prefix[] = new int[n]; // Fill prefix sum array findPrefixSum(prefix, a, n); // Queries int queries[][] = { { 0, 2, 2 }, { 0, 2, 4 }, { 3, 4, 1 }, { 0, 4, 2 } }; int q = queries.length; solveQueries(n, a, b, prefix, queries, q);}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach# Function to create the treedef tree( low, high, pos, b, a, n): # Leaf nodes if (low == high): b[pos] = a[high] return mid = (high + low) // 2 # Left subtree tree(low, mid, 2 * pos + 1, b, a, n) # Right subtree tree(mid + 1, high, 2 * pos + 2, b, a, n) # Merge the maximum b[pos] = max(b[2 * pos + 1], b[2 * pos + 2])# Function that returns the maximum in range L and Rdef rangemax(s, e, low, high, pos, b, a, n): # Complete overlap if (low <= s and high >= e): return b[pos] # Out of range completely if (e < low or s > high): return -(2**32) mid = (s + e) // 2 # Find maximum in left and right subtrees left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n) right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n) # Return the maximum of both return max(left, right)# Function that solves a querydef solveQuery(l, r, k, n, a, b, prefix): # If there are ko if (r - l > k): return -1 # Find maximum in range L and R maximum = rangemax(0, n - 1, l, r, 0, b, a, n) # If maximum is 0 if (maximum < 0): maximum = 0 # Find the prefix sum rangesum = prefix[r] # If not first element if (l > 0): rangesum -= prefix[l - 1] # Get the answer answer = rangesum + (k - (r - l)) * maximum return answer# Function that solves the queriesdef solveQueries( n, a, b, prefix, queries, q): # Solve all the queries for i in range(q): ans = solveQuery(queries[i][0], queries[i][1], queries[i][2], n, a, b, prefix) if (ans != -1): print(ans) else: print("No") # Function to find the prefix sumdef findPrefixSum( prefix, a, n): prefix[0] = a[0] for i in range(1, n): prefix[i] = prefix[i - 1] + a[i]# Driver codea = [1, 3, 2, -4, -5 ]n = len(a)# Array for segment treeb = [0]*(5 * n)# Create segment treetree(0, n - 1, 0, b, a, n)prefix = [0]*n# Fill prefix sum arrayfindPrefixSum(prefix, a, n)# Queriesqueries= [[0, 2, 2],[0, 2, 4],[3, 4, 1],[0, 4, 2]]q = len(queries)solveQueries(n, a, b, prefix, queries, q)# This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to create the treestatic void tree(int low, int high, int pos, int []b, int []a, int n){ // Leaf nodes if (low == high) { b[pos] = a[high]; return; } int mid = (high + low) / 2; // Left subtree tree(low, mid, 2 * pos + 1, b, a, n); // Right subtree tree(mid + 1, high, 2 * pos + 2, b, a, n); // Merge the maximum b[pos] = Math.Max(b[2 * pos + 1], b[2 * pos + 2]);}// Function that returns the maximum in range L and Rstatic int rangemax(int s, int e, int low, int high, int pos, int []b, int []a, int n){ // Complete overlap if (low <= s && high >= e) return b[pos]; // Out of range completely if (e < low || s > high) return int.MinValue; int mid = (s + e) / 2; // Find maximum in left and right subtrees int left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n); int right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n); // Return the maximum of both return Math.Max(left, right);}// Function that solves a querystatic int solveQuery(int l, int r, int k, int n, int []a, int []b, int []prefix){ // If there are ko if (r - l > k) return -1; // Find maximum in range L and R int maximum = rangemax(0, n - 1, l, r, 0, b, a, n); // If maximum is 0 if (maximum < 0) maximum = 0; // Find the prefix sum int rangesum = prefix[r]; // If not first element if (l > 0) rangesum -= prefix[l - 1]; // Get the answer int answer = rangesum + (k - (r - l)) * maximum; return answer;}// Function that solves the queriesstatic void solveQueries(int n, int []a, int []b, int []prefix, int [,]queries, int q){ // Solve all the queries for (int i = 0; i < q; i++) { int ans = solveQuery(queries[i,0], queries[i,1], queries[i,2], n, a, b, prefix); if (ans != -1) Console.WriteLine(ans); else Console.WriteLine("No" ); }}// Function to find the prefix sumstatic void findPrefixSum(int []prefix, int []a, int n){ prefix[0] = a[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; }}// Driver codepublic static void Main(String[] args){ int []a = { 1, 3, 2, -4, -5 }; int n = a.Length; // Array for segment tree int []b = new int[5 * n]; // Create segment tree tree(0, n - 1, 0, b, a, n); int []prefix = new int[n]; // Fill prefix sum array findPrefixSum(prefix, a, n); // Queries int [,]queries = { { 0, 2, 2 }, { 0, 2, 4 }, { 3, 4, 1 }, { 0, 4, 2 } }; int q = queries.GetLength(0); solveQueries(n, a, b, prefix, queries, q);}}// This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach// Function to create the treefunction tree(low,high,pos,b,a,n){ // Leaf nodes if (low == high) { b[pos] = a[high]; return; } let mid = Math.floor((high + low) / 2); // Left subtree tree(low, mid, 2 * pos + 1, b, a, n); // Right subtree tree(mid + 1, high, 2 * pos + 2, b, a, n); // Merge the maximum b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);}// Function that returns the maximum in range L and Rfunction rangemax(s,e,low,high,pos,b,a,n){ // Complete overlap if (low <= s && high >= e) return b[pos]; // Out of range completely if (e < low || s > high) return Number.MIN_VALUE; let mid = Math.floor((s + e) / 2); // Find maximum in left and right subtrees let left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n); let right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n); // Return the maximum of both return Math.max(left, right);}// Function that solves a queryfunction solveQuery(l,r,k,n,a,b,prefix){ // If there are ko if (r - l > k) return -1; // Find maximum in range L and R let maximum = rangemax(0, n - 1, l, r, 0, b, a, n); // If maximum is 0 if (maximum < 0) maximum = 0; // Find the prefix sum let rangesum = prefix[r]; // If not first element if (l > 0) rangesum -= prefix[l - 1]; // Get the answer let answer = rangesum + (k - (r - l)) * maximum; return answer;}// Function that solves the queriesfunction solveQueries(n,a,b,prefix,queries,q){ // Solve all the queries for (let i = 0; i < q; i++) { let ans = solveQuery(queries[i][0], queries[i][1], queries[i][2], n, a, b, prefix); if (ans != -1) document.write(ans+"<br>"); else document.write("No<br>" ); }}// Function to find the prefix sumfunction findPrefixSum(prefix,a,n){ prefix[0] = a[0]; for (let i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + a[i]; }}// Driver codelet a=[1, 3, 2, -4, -5];let n = a.length; // Array for segment treelet b = new Array(5 * n);// Create segment treetree(0, n - 1, 0, b, a, n);let prefix = new Array(n);// Fill prefix sum arrayfindPrefixSum(prefix, a, n);// Querieslet queries = [[ 0, 2, 2 ],[ 0, 2, 4 ],[ 3, 4, 1 ],[ 0, 4, 2 ] ];let q = queries.length;solveQueries(n, a, b, prefix, queries, q);// This code is contributed by rag2127</script> |
Output:
6 12 -9 No
Time Complexity: O(Log N) per query.
Auxiliary Space: O(N log 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!
