Answer: Capgemini OA Question 2024 May | Arrays | on-campus

Solution: Maximum Subarray — Kadane's Algorithm Approach We use Kadane's Algorithm, a classic greedy/DP technique. The key insight is: at any index, we either extend the existing subarray or start a new one from the current element — whichever is larger. Maintain currentSum: the best subarray sum ending at the current position. Maintain maxSum: the global best seen so far. At each element: currentSum = max(num, currentSum + num). If extending is worse than starting fresh, we restart. Update maxSum ...