Максималды қосынды


Күрделілік дәрежесі орта
Жиі кіреді Cisco DE Шоу Dell Фуркиттер Голдман Сакс Грейфтерлер IBM PayU Quora Yahoo
Array Динамикалық бағдарламалау

Проблемалық мәлімдеме

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.

 

Битоникалық субаррядтың максималды қосындысының әдісі

Аңғал көзқарас

Ішкі массивтің сол және оң жақ шекаралары үшін екі көрсеткішті қолдануға болады. Ішкі тізбекті түзеткеннен кейін біз бұл реттіліктің битонды екенін немесе жоқтығын тексереміз. Егер бұл битоникалық субаррея болса, онда біз қосындысын алып, жауапымызды сәйкесінше жаңартамыз. Егер біз осы тәсілді ұстанатын болсақ, бізге үш ұя керек ілмектер бұл мүмкін ең жақсы әдіс емес.

Тиімді тәсіл

Бұл мәселені сызықтық уақыттың күрделілігінде шеше аламыз. Егер біз екі ішкі жиым жасасақ сол және оң, егер бұл біздің шыңымыз қазіргі элемент болса, онда біз сол жаққа қаншалықты алыстап, сол жиымды ith индексінде сақтай аламыз. Қасиетіне дейін сол жаққа қарай жүре аламыз arr [i-1] қанағаттандырылды, сол жақтағы барлық элементтер үшін. Сол сияқты, біз дұрыс субарвар үшін жасаймыз. Енді біз түпнұсқа массивті айналып өтіп, егер біздің қазіргі элементіміз битондық субаррестің шыңы болса, жасалуы мүмкін битондық қосылғыштың максималды қосындысын табамыз. Әр индекс бойынша біз өз жауабымызды жаңартып отырамыз.

Максималды қосындысын табуға арналған код

C ++ коды

#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

 

Java коды

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

Күрделілікті талдау

Уақыттың күрделілігі: O (N)

Біз массив арқылы бір-екі рет өтетіндіктен, ешқандай ілмектер болған жоқ. Бізде уақыттың сызықтық күрделілігі бар.

Ғарыштың күрделілігі: O (N)

Мұнда біз уақытша екі массив жасадық, сол жақтың қосындысы және оң жақ қосындысының өлшемі = енгізу өлшемі. Олар 1-өлшемді массив болғандықтан, бізде сызықтық кеңістіктің күрделілігі де бар.