That was a real stroke of luck. When I got to the coding round and encountered a question on finding the maximum subarray sum, I had literally seen this exact problem on prachub.com a few days earlier. The interview kicked off with a recruiter screen, followed by a technical phone interview. It was intense, especially with the focus on algorithms and data structures. I also faced some behavioral questions that challenged my experience. After a final onsite round, I received an offer and happily accepted. Overall, it was tough but rewarding.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Walk through Kadane's algorithm and explain the O(n) approach.