Maximum sum bitonic subarray

Difficulty Level Medium
Frequently asked in Cisco DE Shaw Dell Fourkites Goldman Sachs Grofers IBM PayU Quora Yahoo
Array Dynamic ProgrammingViews 1427

Problem Statement

An array having n integers is given to us. We need to find the maximum sum bitonic subarray. A bitonic subarray is nothing but just a subarray where the elements are arranged in a specific order. Such that the first elements are in increasing order and then in decreasing order, so something like a, a+1, a+4, a+7, a-9, a-11. Here the constants are just some random numbers that satisfy the conditions imposed on array for being bitonic. Since this is just to show how their ordering is. 

 

Example

Maximum sum bitonic subarray

Size of array = 7

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

Explanation: There are two bitonic arrays possible, one subarray is {1 2 5 4} and the other is {4 10 20 1}. Since we need the maximum sum, we choose the second subarray. And our answer is 4 + 10 + 20 + 1 = 25.

 

Size of array = 4

Array = { 100 200 300 10}
610

Explanation: Since the whole array satisfies our condition of being bitonic. Our answer is 610.

 

Approach for maximum sum bitonic subarray problem

Naive Approach

We can use two pointers for the left and right bounds of the subarray. After fixing the subarray, we check if this sequence is bitonic or not. If this is a bitonic subarray, then we take the sum and update our answer accordingly. If we follow this approach, we need three nested loops which is surely not the best way possible.

Efficient Approach

We can solve this problem in linear time complexity. If we create two sub-arrays left and right, which denotes if our peak is the current element, then how much farther we can go in the left direction and store that sum at ith index of the left array. We can go in the left direction until the property of arr[i-1]<arr[i] is satisfied, for all of the elements in the left direction. Similarly, we do for the right subarray. Now we traverse through our original array and find the maximum sum of the bitonic subarray which can be made if our current element is a peak of the bitonic subarray. At each index, we keep on updating our answer.

Code to find maximum sum bitonic subarray

C++ Code

#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 Code

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

Complexity Analysis

Time Complexity: O(N)

Since we traverse through the array once or twice, and there were no nested loops. We have a linear time complexity.

Space Complexity: O(N)

Here, we made two temporary arrays, leftSum and rightSum of size = inputSize. Since they are 1-dimensional arrays we have a linear space complexity as well.

Translate »