ከፍተኛው ድምር ቢትኒክ ንዑስ ቡድን


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Cisco ዴ ሻው ዴል አራት ኪይትስ ጎልድማን ሳክስ ያወጣል IBM PayU Quora ያሁ
ሰልፍ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ

An ደርድር n ኢንቲጀሮች መኖራቸው ተሰጠን ፡፡ እኛ መፈለግ አለብን ከፍተኛ ድምር ቢቶኒክ ንዑስ ቡድን ቢቶኒክ ንዑስ ቡድን ምንም አይደለም ፣ ንጥረ ነገሮቹ በተወሰነ ቅደም ተከተል የሚዘጋጁበት ንዑስ ቡድን ብቻ ​​ነው። እንደዚህ የመጀመሪያዎቹ ንጥረ ነገሮች በቅደም ተከተል እየጨመሩ እና በመቀጠል ቅደም ተከተል እየቀነሱ ያሉ ናቸው ፣ ስለሆነም እንደ a ፣ a + 1 ፣ a + 4 ፣ a + 7 ፣ a-9 ፣ a-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 ነው ፡፡

 

ለከፍተኛው ድምር ቢቶኒክ ንዑስ ንዑስ ችግር አቀራረብ

የዋህ አቀራረብ

ለሰርቢው ግራ እና ቀኝ ድንበር ሁለት ጠቋሚዎችን መጠቀም እንችላለን ፡፡ ንዑስ መስመሩን ካስተካከልን በኋላ ይህ ቅደም ተከተል ቢቶኒክ መሆን አለመሆኑን እንፈትሻለን ፡፡ ይህ ቢቶኒክ ንዑስ ቡድን ከሆነ እኛ ድምርውን ወስደን መልሳችንን በዚሁ መሠረት እናሻሽላለን። ይህንን አካሄድ ከተከተልን ሶስት ጎጆ ያስፈልገናል ዙሮች ይህ በእርግጥ ከሁሉ የተሻለው መንገድ አይደለም።

ውጤታማ አቀራረብ

ይህንን ችግር በዘመናዊ የጊዜ ውስብስብነት መፍታት እንችላለን ፡፡ ሁለት ንዑስ-ድርሰቶችን ከፈጠርን ግራቀኝ, የእኛ ቁንጮ የአሁኑ ንጥረ ነገር መሆኑን የሚያመለክት ፣ ከዚያ በግራ አቅጣጫው ምን ያህል ርቀን መሄድ እና ያንን ድምር በግራ እድር ማውጫ ላይ ማከማቸት እንችላለን። ንብረቱ እስኪያበቃ ድረስ ወደ ግራ አቅጣጫ መሄድ እንችላለን arr [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-ልኬት ድርድርዎች እኛ እንዲሁ የመስመራዊ የቦታ ውስብስብነት አለን ፡፡