Problem: Maximum Subarray Sum

Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array.

 

For example, in the array

the following subarray produces the maximum sum 10:

We assume that an empty subarray is allowed, so the maximum subarray sum is always at least 0.

Solution:

Remarkably, it is feasible to resolve the problem with linear time complexity, denoted as O(n), indicating that a single iteration is sufficient. The concept involves computing, at every position in the array, the highest sum of a subarray that concludes at that position. Subsequently, the solution to the problem is determined by selecting the highest value among those amounts.

 

Let's examine the subproblem of determining the subarray with the highest total that concludes at position k. There are two potential outcomes: 

1. The subarray solely consists of the element located at position k. 
2. The subarray is composed of a subarray that ends at location k-1, followed by the element at position k. 

In the second scenario, as we aim to identify a subarray with the highest sum, it is crucial for the subarray that concludes at position k-1 to also possess the biggest sum. Therefore, we can easily solve the problem by computing the largest sum of a subarray for each ending location, starting from the left and moving towards the right.

 

The provided code executes the algorithm.

---

Happy Exploring!