## Different Solution Approches

There are many approaches to solving this problem, a few of which are listed below.

**Brute Force:** using three nested loop
**Two-Nested Loop:** By using O(n^{2}) time complexity.
**Divide and Conquer: **similar to merge sort
**Dynamic Programming:** Using O(n) space and O(n) time complexity.
**Kadaneâ€™s Algorithm: **By using O(n) time complexity.

Among the approaches mentioned above, Kadaneâ€™s Algorithm is the most efficient.

In this article, we will discuss Kadaneâ€™s Algorithm, along with pseudo code and code in Carbon Programing Language.

## Kadane's Algorithm

Kadaneâ€™s Algorithm is the optimized approach to solve the maximum sum subarray problem. So, we will apply the dynamic programming idea in this case to optimize the solution. An example of a dynamic programming algorithm is Kadane's Algorithm, which leverages the answers to earlier subproblems to get the best solution.

Let's now examine Kadane's algorithm's operation.

## Working on Kadaneâ€™s Algorithm

In Kadane's technique, the most straightforward concept is to find all contiguous positive segments of the array and keep track of the highest sum contiguous subarray among all positive segments.

- We'll start by thinking about two elements, one of which stores the subarray's maximum end and the other of which stores its maximum sum up to that point.
- Let max_ending_here and max_so_far be these two variables, respectively.
- Both of them will be initialized to 0.
- Every time we receive a positive total, we compare it against max_so_far and, if it exceeds it, update max_so_far.

Read More - __Time Complexity of Sorting Algorithms__

## Code for Kadaneâ€™s Algorithm in Carbon

The following code finds the array's maximum subarray sum using Kadane's Algorithm in Carbon Programming Language.

```
package sample api;
fn Main() -> i32 {
var a: [i32;13] = (1, -11, 9, -2, -3, 7, -2, -2, 1, 5, -2, -9, 1);
var i: i32 = 0;
var mi: i32 = -20000;
var ma: i32 = 0;
while(i<13) {
ma = ma + a[i];
if(mi < ma) {
mi = ma;
}
if(ma < 0) {
ma = 0;
}
i = i+1;
}
Print("{0}", mi);
return 0;
}
```

**Output**:

14

**Time complexity:**

O(n)

**Space Complexity:**

O(1)

Here, the maximum end of the subarray is stored in one element, and its maximum total up to that point is stored in the other.

These two variables should be max ending here (as ma) and max so far (as mi), respectively.

They'll each start with a value of 0.

Every time we get a positive total, we check it against the max and update it if it is higher.

Check out this problem - __Maximum Product Subarray __

## Frequently Asked Questions

**If all of the elements in the array are negative, what should be the maximum subarray sum?**

It depends on whether we are taking an empty subarray into account. The output should be 0 if the subarray is empty; otherwise, it should be the array's maximum element (closest to 0).

**What is the time complexity of Kadaneâ€™s algorithm?**

The time complexity of Kadaneâ€™s algorithm is O(n), where n is the size of the array.

**What is the space complexity of Kadaneâ€™s algorithm?**

The space complexity of Kadaneâ€™s algorithm is O(1) because this algorithm uses constant space.

**Conclusion**

In this article, we have extensively discussed the details of the Maximum Subarray Sum in Carbon along with the details of Kadaneâ€™s Algorithm, the Working of Kadanes Algorithm, and the code of this algorithm in Carbon programming language.

**Recommended problems -**

We hope this article has helped you enhance your knowledge of the Maximum Subarray Sum in Carbon. If you want to learn more, you can refer to our __guided paths__ on the Coding Ninjas Studio platform to learn more about __DSA__, __DBMS__, __Competitive Programming__, __Python__, __Java__, __JavaScript,__ etc. To practice and improve yourself in the interview, you can also check out __Top 100 SQL problems__, __Interview experience__, __Coding interview questions__, and the __Ultimate guide path for interviews__. Do upvote our blog to help other ninjas grow. **Happy Coding!!**