[Kadane's] Maximum Subarray

[sudosf]

Problem

Given an integer array, find the subarray with the largest sum and return its sum.

References

• LeetCode: https://leetcode.com/problems/maximum-subarray/
• GFG: https://www.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1
• Sheet: https://www.risingbrain.org/sheet#array (Kadane's #1)
• Parent: Pattern: Kadane's Algorithm (Arrays) #58

Difficulty

🟡 Medium

Companies

Flipkart, Paytm, PhonePe

Notes

Language: Java
The baseline Kadane's problem. Implement from memory without referencing the template.