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']
Max Sum Contiguous Sub array Asked in: Facebook PayPal Yahoo Microsoft LinkedIn Amazon Goldman Sachs
Find the contiguous subarray within an array, A of length N which has the largest sum.
Input Format:
The first and the only argument contains an integer array, A.
Output Format:
Return an integer representing the maximum possible sum of the contiguous subarray.
Constraints:
1 <= N <= 1e6
-1000 <= A[i] <= 1000
For example:
Input 1:
A = [1, 2, 3, 4, -10]
Output 1:
10
Explanation 1:
The subarray [1, 2, 3, 4] has the maximum possible sum of 10.
Input 2:
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output 2:
6
Explanation 2:
The subarray [4,-1,2,1] has the maximum possible sum of 6.
Solution:
we can use Kadane's Algo O(n) | O(1)
class Solution:# @param A : tuple of integers# @return an integerdef maxSubArray(self, A):s=-(2**30)ans=0for i in A:ans+=iif s<ans:s=ansif ans<0:ans=0return s
Comments
Post a Comment