← Amazon questions

Kadane's Algorithm and Linked-list intersection

Filed under Amazon

Free read 3 of 3

Maintain current_max and global_max. Update current_max as max(num, current_max + num).

The question

Identify and implement Kadane's Algorithm to find the maximum subarray sum in an array, and find the intersection node of two singly linked lists.

Constraints

  • Kadane's: O(N) time, O(1) space
  • Intersection: O(N+M) time, O(1) space

Examples

Input
Kadane: [-2,1,-3,4,-1,2,1,-5,4]
Output
6
Why
The subarray [4,-1,2,1] has the largest sum.

Approach

  1. Maintain current_max and global_max. Update current_max as max(num, current_max + num).

Tips

  • What they are testing: Test Kadane with all negative numbers; test intersection with lists of different lengths.
  • Common mistake: In intersection, failing to reset pointers after reaching the end of the first list.

Follow-ups

  • Given a tree with only parent pointers, how to find the LCA?

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.