Optimal Subarray selection Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 17

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

Let pref[i] denote the sum of first i elements of the array. Let prefMin[i] denote the minimum of pref[1], pref[2], pref[3]...., pref[i]. Let suffMax[i] denote the maximum of pref[i], pref[i+1], pref[i+2]....., pref[N].
For a query [B[i][0], B[i][1]] the subarray has to start on or before B[i][0] and end on or after B[i][1]. The sum of a subarray starting at index x and ending at index y is pref[y]-pref[x-1].
We can see we have to take the maximum pref[y] for y and minimum pref[x-1] for x in order to maximize the sum so the answer to the query would be suff Max[B[i][1]] - pref Min[B[i][0]-1].

Time Complexity - O(N+Q) Space Complexity - O(N)