kunjaan
BAN USERMaximum sum of the sub array can be done in number of ways depending on the time complexity needed, the space constraint and preprocessing allowed.
It can be done in a straight forward way by adding the positive numbers as you see them. Then once you see a negative number, start adding the negative numbers and store the positive number as temp_max. At the end of the negative number run,see if the sum of negative number hurts or adds to the temp_max. If it hurts, exclude the negative number else add to temp_max. Continue until you see all the numbers. A separate bookkeeping variable for positions is required. The time is O(n).
It can also be done using a Dynamic Programming approach, where the core recursive solution consists of storing the value of maximum sum seen so far for each number. Everytime you see another number, the decision involves either taking the number to increase the previous sum or not. However this approach requires O(n^2).
It can be done in O(n) by converting the numbers into nodes, the edges become the weight of the number. Add a dummy source which links to all the nodes via a weighted edge where the weight is the number is itself. (s->1 has an edge weight 1). Add a dummy destination, which links to all the nodes except the source via an edge weight of 0. Now the problem reduces to finding the Longest Path in the Directed Acyclic Graph.
Assuming Longest Path of the tree is the diameter of the tree, the distance from the the root to its leaf.
- kunjaan May 17, 2009Start from an arbitrary node and run a Bread First Search. Note the last node visited. From this node, run a BFS again. The distance from this node to the last node visited is the diameter of the tree.