from collections import defaultdict graph=defaultdict(list) v,e=map(int,input().split()) for i in range(e): u,v=map(str,input().split()) graph[u].append(v) graph[v].append(u) for i in graph: print(i,"->",graph[i]) Input: 7 9 A B A C A F C E C F C D D E D G G F Output: F -> ['A', 'C', 'G'] C -> ['A', 'E', 'F', 'D'] G -> ['D', 'F'] D -> ['C', 'E', 'G'] A -> ['B', 'C', 'F'] E -> ['C', 'D'] B -> ['A']
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 <= 105.
1 <= A[i] <= 108.
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:
Fastest :
from bisect import bisect_left
def BinarySearch(a, x):
i = bisect_left(a, x)
if i:
return (i-1)
else:
return -1
class Solution:
# @param A : list of integers
# @return an integer
def solve(self, A):
n=len(A)
dp=[0]*n
dp[n-1]=A[n-1]
for i in range(n-2,-1,-1):
dp[i]=max(dp[i+1],A[i])
lst=[]
maxe=0
lst.append(A[0])
for i in range(1,n-1):
res = BinarySearch(lst, A[i])
if(res!=-1):
if dp[i+1]<=A[i]:
continue
ans=lst[res] + A[i] + dp[i+1]
maxe=max(maxe,ans)
lst.insert(res+1,A[i])
return maxe
return 0
return ans
Solution credits:
To insert the element and maintain the asceding order of the array then we need to use bisect:
Bisect Study link: https://www.geeksforgeeks.org/bisect-algorithm-functions-in-python/
Comments
Post a Comment