Horje
Find Maximum Sum of Mountain Triplets

Given an array A[] of integers. Then the task is to output the maximum sum of a triplet (Ai, Aj, Ak) such that it must follow the conditions: (i < j < k) and (Ai < Aj > Ak). If no such triplet exists, then output -1.

Examples:

Input: A[] = {1, 5, 4, 7, 3}

Output: 15

Explanation: There are following 6 possible triplets following the condition (i < j < k) and (Ai < Aj > Ak):

  • (A1, A2, A3): Sum = 1 + 5 + 4 = 10
  • (A1, A2, A5): Sum = 1 + 5 + 3 = 13
  • (A1, A3, A5): Sum = 1 + 4 + 3 = 8
  • (A1, A4, A5): Sum = 1 + 7 + 3 = 11
  • (A2, A4, A5): Sum = 5 + 7 + 3 = 15
  • (A3, A4, A5): Sum = 4 + 7 + 3 = 14

It is clearly visible the maximum sum is 15, given by the triplet (A2, A4, A5). Therefore, output is 15.

Input: A[] = {2, 1, 3, 4}

Output: -1

Explanation: No valid triplet exists following both of given conditions. Therefore, output is -1.

Brute Force Approach: The basic idea to solve the problem is as follows:

Use 3 nested loops to iterate over all possible triplets following the conditions (i < j < k) and (Ai < Aj > Ak).

Steps were taken to solve the problem:

  • Create a variable let say MaxSum to store the maximum sum of triplet.
  • Run 3 nested loops to create all possible triplets and follow the condition inside the innermost nested loop:
    • If (Aj > Ai && Aj > Ak)
      • Sum = Ai + Aj + Ak
      • MaxSum = max(Sum, MaxSum)
  • If (MaxSum == 0), then return -1 else return MaxSum.

Code to implement the approach:

C++

#include <iostream>
using namespace std;
 
// Function to return maximum sum of triplet if it exists
int MaxTripletSum(int A[], int N)
{
    // Variable to store max sum
    int maxSum = 0;
 
    // Three nested loops to iterate over all possible triplets
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
 
                // Checking for the condition mentioned
                if (A[j] > A[i] && A[j] > A[k]) {
                    // Adding elements of triplets
                    int sum = A[i] + A[j] + A[k];
 
                    // Updating max if sum is greater than max
                    maxSum = max(maxSum, sum);
                }
            }
        }
    }
 
    // Returning maxSum if triplet exists, else returning -1
    return maxSum == 0 ? -1 : maxSum;
}
 
// Driver Function
int main()
{
    // Input A[]
    int A[] = {1, 5, 4, 7, 3};
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function call
    cout << MaxTripletSum(A, N) << endl;
 
    return 0;
}

Java

// Java code to implement the brute
// force approach
 
// Driver Class
class Main {
 
    // Driver Function
    public static void main(String[] args)
    {
        // Input A[]
        int A[] = { 1, 5, 4, 7, 3 };
 
        // Function call
        System.out.print(MaxTripletSum(A));
    }
 
    // Method to return maximum sum of triplet
    // If it exists
    static int MaxTripletSum(int[] A)
    {
 
        int N = A.length;
 
        // Variable to store max sum
        int maxSum = 0;
 
        // Three nested loops for iterate over
        // all possible triplets
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
 
                    // Checking for the condition
                    // mentioned
                    if (A[j] > A[i] && A[j] > A[k]) {
                        // Adding element of
                        // triplets
                        int sum = A[i] + A[j] + A[k];
 
                        // Updating max if sum is
                        // greater than max
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }
 
        // Returning maxSum if triplet exists
        // Else returning -1
        return maxSum == 0 ? -1 : maxSum;
    }
}

C#

using System;
 
class GFG {
    // Driver Function
    public static void Main(string[] args)
    {
        // Input A[]
        int[] A = { 1, 5, 4, 7, 3 };
 
        // Function call
        Console.Write(MaxTripletSum(A));
    }
 
    // Method to return maximum sum of triplet
    // If it exists
    static int MaxTripletSum(int[] A)
    {
        int N = A.Length;
 
        // Variable to store max sum
        int maxSum = 0;
 
        // Three nested loops for iterate over
        // all possible triplets
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    // Checking for the condition
                    // mentioned
                    if (A[j] > A[i] && A[j] > A[k]) {
                        // Adding element of
                        // triplets
                        int sum = A[i] + A[j] + A[k];
 
                        // Updating max if sum is
                        // greater than max
                        maxSum = Math.Max(maxSum, sum);
                    }
                }
            }
        }
 
        // Returning maxSum if triplet exists
        // Else returning -1
        return maxSum == 0 ? -1 : maxSum;
    }
}

Javascript

// JavaScript code to implement the brute
// force approach
 
// Function to return maximum sum
// of triplet if it exists
function MaxTripletSum(A) {
    const N = A.length;
 
    // Variable to store max sum
    let maxSum = 0;
 
    // Three nested loops for iterating
    // over all possible triplets
    for (let i = 0; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
            for (let k = j + 1; k < N; k++) {
                // Checking for the condition mentioned
                if (A[j] > A[i] && A[j] > A[k]) {
                // Adding elements of triplets
                    const sum = A[i] + A[j] + A[k];
 
                    // Updating max if sum is greater than max
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }
    }
 
    // Returning maxSum if triplet
    // exists, else returning -1
    return maxSum === 0 ? -1 : maxSum;
}
 
// Input A[]
const A = [1, 5, 4, 7, 3];
 
// Function call
console.log(MaxTripletSum(A));

Python3

# Python code to implement the brute
# force approach
 
def max_triplet_sum(arr):
    n = len(arr)
    max_sum = 0
 
    # Three nested loops to iterate over all possible triplets
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                # Checking for the condition mentioned
                if arr[j] > arr[i] and arr[j] > arr[k]:
                    # Adding elements of triplets
                    _sum = arr[i] + arr[j] + arr[k]
 
                    # Updating max if sum is greater than max
                    max_sum = max(max_sum, _sum)
 
    # Returning max_sum if triplet exists, else returning -1
    return max_sum if max_sum != 0 else -1
 
# Driver code
if __name__ == "__main__":
    # Input array A
    A = [1, 5, 4, 7, 3]
 
    # Function call
    result = max_triplet_sum(A)
     
    print(result)

Output

15

Time Complexity: O(N3)
Auxiliary Space: O(1)

Efficient approach: To solve the problem follow the below idea:

Create an array let say LeftMax[] and for each index i(2 <= i <= N) store the maximum value from the range [A1, Ai-1] at ith index of leftMax[] and initialize leftMax1 as A1. After that run a loop from right end of A[] and simultaneously calculate max element to right from the current index in a variable let say RightMax. If the condition (leftMax[i] < A[i] > RightMax) met, then triplet (leftMax[i], A[i], RightMax) is valid triplet, calculate the sum of all 3 elements and update it with MaxSum.

Steps were taken to solve the problem:

  • If (length of A == 3) and middle element is biggest then return sum of all 3 elements else return -1.
  • Create an array let say LeftMax[] of length N.
  • leftMax[1] = A[1]
  • Run a loop for i = 1 to i < N and follow below mentioned steps under the scope of loop:
    • leftMax[i] = Math.max(leftMax[i – 1], A[i – 1])
  • Create a variable let say MaxSum to store maximum sum of triplet.
  • Create a variable let say RightMax to store max element to right and initialize it with A[N-1].
  • Run a loop for i = N – 2 to i > 0 and follow below mentioned steps under the scope of loop:
    • RightMax = Math.min(RightMax, A[i + 1])
    • If (A[i] > leftMax[i] && A[i] > RightMax)
      • MaxSum = Math.max(MaxSum, leftMaxs[i] + nums[i] + rightMax)
  • If (maxSum == Integer.MIN_VALUE), then return -1 else return MaxSum

Code to implement the approach:

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
 
using namespace std;
 
// Function to return max sum of valid triplet
int maxTripletSum(vector<int>& A)
{
    // Variable to store length of A[]
    int N = A.size();
 
    // Case, when length of A = 3
    if (N == 3) {
        int sum = A[0] + A[1] + A[2];
        return (A[1] > A[0] && A[1] > A[2]) ? sum : -1;
    }
 
    // leftMax Array
    vector<int> leftMaxs(N);
 
    // Initializing first element as same as
    // A[0] because no left max element exists
    leftMaxs[0] = A[0];
 
    // Initializing leftMax array
    for (int i = 1; i < N; i++)
        leftMaxs[i] = max(leftMaxs[i - 1], A[i - 1]);
 
    // Variable to store max Sum of triplet
    int maxSum = INT_MIN;
 
    // Variable to store max element to right
    int rightMax = A[N - 1];
 
    // Loop to iterate over A and
    // implement approach
    for (int i = N - 2; i > 0; i--) {
        rightMax = min(rightMax, A[i + 1]);
        if (A[i] > leftMaxs[i] && A[i] > rightMax)
            maxSum = max(maxSum, leftMaxs[i] + A[i] + rightMax);
    }
 
    // Returning the max sum
    return (maxSum == INT_MIN) ? -1 : maxSum;
}
 
// Drivers code
int main()
{
    vector<int> nums = {1, 5, 4, 7, 3};
 
    // Function Call
    cout << maxTripletSum(nums) << endl;
 
    return 0;
}
//This code is contributed by Aman.

Java

// Java code to implement the approach
 
import java.util.*;
 
// Driver Class
class Main {
 
    // Method to return max sum of valid triplet
    static int maxTripletSum(int[] A)
    {
 
        // Variable to store length of A[]
        int N = A.length;
 
        // Case, when length of A = 3
        if (N == 3) {
            int sum = A[0] + A[1] + A[2];
            return (A[1] > A[0] && A[1] > A[2]) ? sum : -1;
        }
 
        // leftMax Array
        int[] leftMaxs = new int[N];
 
        // Initilalzing first element as same as
        // A[0] because no left max element exists
        leftMaxs[0] = A[0];
 
        // Initilaizing leftMax array
        for (int i = 1; i < N; i++)
            leftMaxs[i]
                = Math.max(leftMaxs[i - 1], A[i - 1]);
 
        // Variable to store max Sum of triplet
        int maxSum = Integer.MIN_VALUE;
 
        // Variable to store max element to right
        int rightMax = A[N - 1];
 
        // Loop to iterate over A and
        // implement approach
        for (int i = N - 2; i > 0; i--) {
            rightMax = Math.min(rightMax, A[i + 1]);
            if (A[i] > leftMaxs[i] && A[i] > rightMax)
                maxSum = Math.max(maxSum, leftMaxs[i] + A[i]
                                            + rightMax);
        }
 
        // Returning the max sum
        return (maxSum == Integer.MIN_VALUE) ? -1 : maxSum;
    }
 
    // Drivers code
    public static void main(String[] args)
    {
        int nums[] = { 1, 5, 4, 7, 3 };
 
        // Function Call
        System.out.print(maxTripletSum(nums));
    }
}

C#

using System;
 
class MainClass
{
    // Method to return max sum of valid triplet
    static int MaxTripletSum(int[] A)
    {
        // Variable to store length of A[]
        int N = A.Length;
 
        // Case, when length of A = 3
        if (N == 3)
        {
            int sum = A[0] + A[1] + A[2];
            return (A[1] > A[0] && A[1] > A[2]) ? sum : -1;
        }
 
        // leftMax Array
        int[] leftMaxs = new int[N];
 
        // Initializing first element as same as
        // A[0] because no left max element exists
        leftMaxs[0] = A[0];
 
        // Initializing leftMax array
        for (int i = 1; i < N; i++)
            leftMaxs[i] = Math.Max(leftMaxs[i - 1], A[i - 1]);
 
        // Variable to store max Sum of triplet
        int maxSum = int.MinValue;
 
        // Variable to store max element to right
        int rightMax = A[N - 1];
 
        // Loop to iterate over A and
        // implement the approach
        for (int i = N - 2; i > 0; i--)
        {
            rightMax = Math.Min(rightMax, A[i + 1]);
            if (A[i] > leftMaxs[i] && A[i] > rightMax)
                maxSum = Math.Max(maxSum, leftMaxs[i] + A[i] + rightMax);
        }
 
        // Returning the max sum
        return (maxSum == int.MinValue) ? -1 : maxSum;
    }
 
    // Drivers code
    public static void Main(string[] args)
    {
        int[] nums = { 1, 5, 4, 7, 3 };
 
        // Function Call
        Console.Write(MaxTripletSum(nums));
    }
}

Javascript

// Function to return max sum of valid triplet
function maxTripletSum(A) {
 
    // Variable to store length of A[]
    const N = A.length;
 
    // Case, when length of A = 3
    if (N === 3) {
        const sum = A[0] + A[1] + A[2];
        return (A[1] > A[0] && A[1] > A[2]) ? sum : -1;
    }
 
    // leftMax Array
    const leftMaxs = new Array(N);
 
    // Initializing first element as same as
    // A[0] because no left max element exists
    leftMaxs[0] = A[0];
 
    // Initializing leftMax array
    for (let i = 1; i < N; i++)
        leftMaxs[i] = Math.max(leftMaxs[i - 1], A[i - 1]);
 
    // Variable to store max Sum of triplet
    let maxSum = Number.MIN_SAFE_INTEGER;
 
    // Variable to store max element to right
    let rightMax = A[N - 1];
 
    // Loop to iterate over A and implement approach
    for (let i = N - 2; i > 0; i--) {
        rightMax = Math.min(rightMax, A[i + 1]);
        if (A[i] > leftMaxs[i] && A[i] > rightMax)
            maxSum = Math.max(maxSum, leftMaxs[i] + A[i] + rightMax);
    }
 
    // Returning the max sum
    return (maxSum === Number.MIN_SAFE_INTEGER) ? -1 : maxSum;
}
 
// Driver code
const nums = [1, 5, 4, 7, 3];
 
// Function Call
console.log(maxTripletSum(nums));

Python3

# Python code to implement the approach
 
# Method to return max sum of valid triplet
def max_triplet_sum(A):
    # Variable to store length of A[]
    N = len(A)
 
    # Case, when length of A = 3
    if N == 3:
        sum_value = A[0] + A[1] + A[2]
        return sum_value if A[1] > A[0] and A[1] > A[2] else -1
 
    # leftMax Array
    left_maxs = [0] * N
 
    # Initializing first element as same as
    # A[0] because no left max element exists
    left_maxs[0] = A[0]
 
    # Initializing leftMax array
    for i in range(1, N):
        left_maxs[i] = max(left_maxs[i - 1], A[i - 1])
 
    # Variable to store max Sum of triplet
    max_sum = float('-inf')
 
    # Variable to store max element to right
    right_max = A[N - 1]
 
    # Loop to iterate over A and implement the approach
    for i in range(N - 2, 0, -1):
        right_max = min(right_max, A[i + 1])
        if A[i] > left_maxs[i] and A[i] > right_max:
            max_sum = max(max_sum, left_maxs[i] + A[i] + right_max)
 
    # Returning the max sum
    return max_sum if max_sum != float('-inf') else -1
 
# Driver code
nums = [1, 5, 4, 7, 3]
 
# Function Call
print(max_triplet_sum(nums))

Output

15

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Construct MST from GCD Construct MST from GCD
Minimizing Total Cost for MEX Reduction Minimizing Total Cost for MEX Reduction
Minimum number of nodes to be selected to light up all the edges of the tree (Select Nodes) Minimum number of nodes to be selected to light up all the edges of the tree (Select Nodes)
Basic Geometry for Competitive Programming Basic Geometry for Competitive Programming
Suffix Arrays for Competitive Programming Suffix Arrays for Competitive Programming

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje