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 of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].
Input Format
First and only argument is an integer array A.
Output Format
Return an integer denoting the maximum value of j - i;
Example Input
Input 1:
A = [3, 5, 4, 2]
Example Output
Output 1:
2
Example Explanation
Explanation 1:
Maximum value occurs for pair (3, 4).
Solution:
class Solution:
# @param A : tuple of integers
# @return an integer
def maximumGap(self, A):
n=len(A)
R = [0] * n
R[n - 1] = A[n - 1]
for j in range(n - 2, -1, -1):
R[j] = max(A[j], R[j + 1]);
i = 0;j=0
diff = -1
while (j < n and i < n):
if (A[i] <= R[j]):
diff = max(diff, j - i)
j+=1
else:
i+=1
return diff
Comments
Post a Comment