1.
Introduction
2.
What is the maximum sum subarray?
3.
Different Solution Approches
4.
5.
6.
Code for Kadaneâ€™s Algorithm in Carbon
6.1.
Output:
6.2.
Time complexity:
6.3.
Space Complexity:
7.
7.1.
If all of the elements in the array are negative, what should be the maximum subarray sum?
7.2.
What is the time complexity of Kadaneâ€™s algorithm?
7.3.
What is the space complexity of Kadaneâ€™s algorithm?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Maximum Subarray Sum in Carbon

Nilesh Kumar
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

## Introduction

Maximum Subarray Sum is a well-known problem in which we must identify a contiguous subarray whose sum is the highest among all subarrays for the given array. One needs to be familiar with Kadane's algorithm to solve this. In this article, we will discuss the maximum subarray sum in Carbon. A successor to C++ that offers developers a specific entry point to a more advanced language that handles modern development ideas like memory safety and generics is the Carbon Language.

## What is the maximum sum subarray?

An array's continuous component is known as a subarray. It could be a single array element or a portion of the array. A subarray with the maximum sum value is referred to as the largest sum contiguous subarray.

For example

An array is [-23, 5, 1, 8, -9, 2, -7, 3, -11]. Its sub-arrays can be [-23,5,1,8] or [5,1,8] or [2,-7,3, -11], etc. But since [5,1,8,3] is not maintaining the sequences, it cannot be a subarray.

Among all the subarrays, the one indicated in the following subarray [5,1,8] has the highest summation value.

The sum of the sub-array [5,1,8] = 14 is the maximum sum in all possible combinations of the subarray of the above array.

So, for this array, the maximum subarray is [5,1,6].

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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(n2) 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 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.

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;
}``````

14

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.

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

### 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 DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. To practice and improve yourself in the interview, you can also check out Top 100 SQL problemsInterview experienceCoding interview questions, and the Ultimate guide path for interviews. Do upvote our blog to help other ninjas grow. Happy Coding!!

Live masterclass