SeaCode

Appearance

Maximum Sum Triplet ​

Problem Description ​

Given an array A containing N integers.

You need to find the maximum sum of triplet ( Ai + Aj + Ak ) such that 0 <= i < j < k < N and Ai < Aj < Ak.

If no such triplet exist return 0.

Problem Constraints

3 <= N <= 10^5.
1 <= A[i] <= 10^8.

Input Format

First argument is an integer array A.

Output Format

Return a single integer denoting the maximum sum of triplet as described in the question.

Example Input

Input 1:
 A = [2, 5, 3, 1, 4, 9]

Input 2:
 A = [1, 2, 3]

Example Output

Output 1:
 16

Output 2:
 6

Example Explanation

Explanation 1:
 All possible triplets are:-
    2 3 4 => sum = 9
    2 5 9 => sum = 16
    2 3 9 => sum = 14
    3 4 9 => sum = 16
    1 4 9 => sum = 14
  Maximum sum = 16

Explanation 2:
 All possible triplets are:-
    1 2 3 => sum = 6
 Maximum sum = 6

Solution ​

swift
import Foundation

class Solution {
        
    func insert(_ A: inout [Int], _ B:Int) -> Int {
        var l = 0
        var r = A.count-1
        while l<=r {
            var m = (l+r)/2
            if A[m] == B {
                A.insert(B, at:m)
                while m >= 1 {
                    m -= 1
                    if A[m] < B{
                        return A[m]
                    }
                } 
                return 0
            } else if A[m] < B {
                l = m + 1
            } else {
                r = m - 1
            }
        }
        
        if r < 0 {
            A.insert(B,at:0)
            return 0
        } else if l >= A.count {
            A.append(B)
            return A[A.count-2]
        } else {
            A.insert(B,at:l)
            return A[r]
        }
        
        return 0
    }
    
	func solve(_ A: inout [Int]) -> Int {
        let len = A.count
        var ret = 0
            
        var rights = [Int](repeating:0,count:len)
        rights[len-1] = 0 
        for i in (0..<(len-1)).reversed() {
            var r = max(A[i+1],rights[i+1])
            if r > A[i]{
                rights[i] = r
            }
        }
        
        var lefts = [Int]()
        lefts.append(A[0])
        for i in 1..<(len-1) {
            let l = insert(&lefts,A[i])
            
            if l == 0 || rights[i] == 0 {
                continue
            }
            ret = max(ret, l + A[i] + rights[i] )
        }
        return ret
	}
}

References ​