Software Engineer

First, let us initialize a variable say sum = 0 which stores the sum of elements traversed so far and another variable says max = 0 which stores the length of the longest subarray with sum zero. Declare a HashMap which stores the prefix sum of every element as a key and its index as a value. Now traverse the array, and add the array element to our sum.

• Map: Stores the first node at each vertical index (key = vertical, value = node).
• Queue: Perform BFS, storing nodes with their vertical indices.
• BFS Steps:
  • Dequeue node; if vertical not in map, add it.
  • Enqueue left child with vertical-1, right child with vertical+1.
• Result: Sort map by vertical index to get the top view.

Kadane’s Algorithm Approach:
We iterate through the given array using a single loop and maintain a variable sum to store the sum of the current subarray. At each step, we add the current element to sum. If sum becomes negative at any point, we reset it to 0, since a negative sum would decrease the sum of any subsequent subarray. During the iteration, we keep track of the maximum sum encountered so far and return it as the result.

Note: If the array contains all negative numbers, initialize maxSum with the first element to ensure correctness.