Maximum Subarray Problem Solutions

The "Maximum Subarray" problem is a classic example in computer science, used to illustrate dynamic programming as well as divide and conquer strategies. It involves finding a contiguous subarray with the largest sum in a given array.

Dynamic Programming Solution

The dynamic programming approach, also known as Kadane's algorithm, iteratively computes the maximum subarray sum ending at each position.

Divide and Conquer Solution

The divide and conquer approach splits the array into two halves and recursively finds the maximum subarray sum in each half. It also considers the possibility of the maximum subarray crossing the midpoint.

Explanation

• Dynamic Programming: This approach iteratively updates a running sum and maximum sum, resetting the running sum if it becomes negative.
• Divide and Conquer: This method recursively solves the problem in subarrays and finds the maximum sum that crosses the middle of the array. Both methods offer a way to understand different algorithmic strategies and their applications in solving complex problems.

Rust Solution

Rust's for &num in &nums iterates over a borrow of the vector instead of consuming it, and the &num pattern destructures each reference into a copied i32, so cur_sum += num adds a value rather than a reference. Where the TypeScript reached for Math.max, Rust calls the .max method directly on the integer in max_sub.max(cur_sum). The Vec<i32> argument is taken by value while &nums re-borrows it for the loop, and the function yields max_sub as a bare tail expression with no return keyword.

Go Solution

Go's for _, num := range nums uses the blank identifier _ to drop the index that a range over a []int yields, keeping only the element. The running maximum is updated with an explicit if curSum > maxSub block rather than the Math.max the TypeScript version used. Locals arrive through := short declarations, and the answer leaves via an explicit return maxSub.