जास्तीत जास्त बेटोनिक सबअरे


अडचण पातळी मध्यम
वारंवार विचारले सिस्को डीई शॉ डेल फोरकाइट्स गोल्डमन Sachs ग्रॉफर्स IBM पीएयू Quora याहू
अरे डायनॅमिक प्रोग्रामिंग

समस्या विधान

An अॅरे पूर्णांक संख्या आम्हाला दिली आहे. आम्हाला शोधणे आवश्यक आहे जास्तीत जास्त बेटोनिक सबराय. एक बिटोनिक सबर्रे हे केवळ एक सबअरे नसून जिथे घटक एका विशिष्ट क्रमाने तयार केले जातात. असे की प्रथम घटक वाढत्या क्रमाने आणि नंतर घटत्या क्रमाने असतात, म्हणून अ, ए +1, अ + 4, अ + 7, ए -9, ए -11 सारखे काहीतरी. येथे स्थिरांक फक्त काही यादृच्छिक संख्या आहेत जी अ‍ॅटेवर बीटोनिक असल्याच्या अटी लागू करतात. हे त्यांचे ऑर्डर कसे आहे ते दर्शविण्यासाठीच आहे. 

 

उदाहरण

जास्तीत जास्त बेटोनिक सबअरे

Size of array = 7

Array = {1 2 5 4 10 20 1}
25

स्पष्टीकरणः दोन बिटोनिक अ‍ॅरे शक्य आहेत, एक सबर्रे {1 2 5 4} आणि दुसरा {4 10 20 1} आहे. आम्हाला जास्तीत जास्त बेरीज आवश्यक असल्याने आम्ही दुसरा सबअरे निवडतो. आणि आमचे उत्तर 4 + 10 + 20 + 1 = 25 आहे.

 

Size of array = 4

Array = { 100 200 300 10}
610

स्पष्टीकरणः संपूर्ण अ‍ॅरे आमच्या बिटोनिक होण्याच्या स्थितीस समाधानी करीत आहे. आमचे उत्तर 610 आहे.

 

जास्तीत जास्त बेटोनिक सबरीच्या समस्येसाठी दृष्टिकोण

भोळे दृष्टिकोन

सबबारच्या डाव्या आणि उजव्या सीमेसाठी आम्ही दोन पॉईंटर्स वापरू शकतो. सबर्रे निश्चित केल्यानंतर, आम्ही हे क्रम बिटोनिक आहे की नाही ते तपासतो. जर हे बिटोनिक सबअरे असेल तर आम्ही बेरीज घेऊ आणि त्यानुसार आपले उत्तर अद्यतनित करू. जर आपण हा दृष्टिकोन पाळत राहिलो तर आपल्याला तीन नेस्टेड आवश्यक आहेत लूप हा नक्कीच उत्तम मार्ग नाही.

कार्यक्षम दृष्टीकोन

आम्ही ही समस्या रेषीय वेळेच्या जटिलतेमध्ये सोडवू शकतो. जर आपण दोन उप-अ‍ॅरे तयार केल्या तर बाकी आणि बरोबर, जे दर्शविते की जर आपला शिखर वर्तमान घटक असेल तर आपण किती पुढे जाऊ शकतो आणि डावीकडील अ‍ॅरेच्या इथ इंडेक्समध्ये किती बेरीज ठेवू शकतो. च्या मालमत्तेपर्यंत आम्ही डावीकडे जाऊ शकतो अरे [i-1] डावीकडील सर्व घटकांसाठी समाधानी आहे. त्याचप्रमाणे आम्ही योग्य सबर्रेसाठी करतो. आता आम्ही आमच्या मूळ अ‍ॅरेमधून पुढे जात आहोत आणि बीटॉनिक सबॅरेची जास्तीत जास्त बेरीज शोधू शकतो जी आपला सद्य घटक बिटोनिक सबॅरेचा शिखर असल्यास बनविला जाऊ शकतो. प्रत्येक निर्देशांकात आम्ही आपले उत्तर अद्यतनित करत राहतो.

जास्तीत जास्त बेटोनिक सबराय शोधण्यासाठी कोड

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;


int main(){
    int testCases;cin>>testCases;
    while(testCases--){
    	int inputSize;cin>>inputSize;
    	long long int input[inputSize];
    	for(int i=0;i<inputSize;i++){
    		cin>>input[i];
        }
        
        long long int leftSum[inputSize], rightSum[inputSize];
        for(int i=0;i<inputSize;i++)
        	leftSum[i] = rightSum[i] = input[i];
        
        leftSum[0] = input[0];
        for(int i=1;i<inputSize;i++){
        	if(input[i-1] < input[i])
        		leftSum[i] += leftSum[i-1];
        }
        
        rightSum[inputSize-1] = input[inputSize-1];
        for(int i=inputSize-2;i>=0;i--){
        	if(input[i] > input[i+1])
        		rightSum[i] += rightSum[i+1];
        }
        
        long long int answer = LLONG_MIN;
        for(int i=0;i<inputSize;i++){
        	answer = max(answer, leftSum[i] + rightSum[i] - input[i]);
        }
        cout<<answer<<endl;
    }
    return 0;
}
2
5
1 2 5 3 10
5
10 50 10 90 10
13
110

 

जावा कोड

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

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while(testCases-- > 0){
        	int inputSize = sc.nextInt();
        	long input[] = new long[inputSize];
        	for(int i=0;i<inputSize;i++){
        		input[i] = sc.nextInt();
            }
            
            long leftSum[] = new long[inputSize];
            long rightSum[] = new long[inputSize];
            for(int i=0;i<inputSize;i++) {
            	leftSum[i] = input[i];
            	rightSum[i] = input[i];
            }
            
            leftSum[0] = input[0];
            for(int i=1;i<inputSize;i++){
            	if(input[i-1] < input[i])
            		leftSum[i] += leftSum[i-1];
            }
            
            rightSum[inputSize-1] = input[inputSize-1];
            for(int i=inputSize-2;i>=0;i--){
            	if(input[i] > input[i+1])
            		rightSum[i] += rightSum[i+1];
            }
            
            long answer = Long.MIN_VALUE;
            for(int i=0;i<inputSize;i++){
            	answer = Math.max(answer, leftSum[i] + rightSum[i] - input[i]);
            }
            System.out.println(answer);
        }
    }
}
2 
5 
1 2 5 3 10 
5 
10 50 10 90 10
13
110

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी: ओ (एन)

आम्ही अ‍ॅरेमधून एक किंवा दोन वेळा आच्छादित केल्यामुळे आणि तेथे नेस्टेड लूप नव्हते. आमच्याकडे रेषीय वेळ गुंतागुंत आहे.

स्पेस कॉम्प्लेक्सिटी: ओ (एन)

येथे आम्ही दोन तात्पुरते अ‍ॅरे, लेफ्टसम आणि राइट्सम आकार = इनपुटसाइझ केले. ते 1-द्विमितीय अ‍ॅरे असल्यामुळे आमच्याकडे देखील एक रेखीय स्पेस कॉम्प्लेक्स आहे.