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

Brute-force Approach

Iterate through all subarrays, calculating its sum, and finding the maximum sum.

Time: O(n^3)

Space: O(1)

Better Approach

Get rid of the third loop by maintaining a running sum to calculate the sum of subarrays starting at a particular index.

Time: O(n^2)

Space: O(1)

Optimal Approach

Kadane's Algorithm: Maintain a running sum and update the maximum sum at each index. If the running sum becomes negative, reset it to 0, as it will never contribute to the maximum sum.

Time: O(n)

Space: O(1)