Максимальна сума бітонічного підмасиву


Рівень складності Medium
Часто запитують у Cisco Д. Е. Шоу Dell Фуркіти Goldman Sachs Грофери IBM PayU Quora Yahoo
масив Динамічне програмування

Постановка проблеми

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.

 

Підхід до задачі максимальної суми бітонічного підмасиву

Наївний підхід

Ми можемо використовувати два покажчики для лівої та правої меж підмасиву. Після фіксації підмасиву ми перевіряємо, чи є ця послідовність бітонічною чи ні. Якщо це бітонічний підмасив, тоді ми беремо суму і відповідно оновлюємо нашу відповідь. Якщо ми дотримуємося цього підходу, нам потрібні три вкладених петлі що, безумовно, не найкращий із можливих способів.

Ефективний підхід

Ми можемо вирішити цю проблему в лінійній часовій складності. Якщо ми створимо два підмасиви залишити і право, що позначає, якщо наш пік - це поточний елемент, то на скільки далі ми можемо піти вліво і зберегти цю суму за i-м індексом лівого масиву. Ми можемо їхати в лівому напрямку до майна 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

 

Код 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)

Тут ми створили два тимчасові масиви, leftSum і rightSum size = inputSize. Оскільки це одновимірні масиви, ми також маємо лінійну складність простору.