Table of contents
1.
Introduction
2.
What is the maximum sum subarray?
3.
Different Solution Approches
4.
Kadane's Algorithm
5.
Working on Kadane’s Algorithm
6.
Code for Kadane’s Algorithm in Carbon
6.1.
Output:
6.2.
Time complexity:
6.3.
Space Complexity:
7.
Frequently Asked Questions
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

Author Nilesh Kumar
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

Maximum Subarray Sum in Carbon

 

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].

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

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 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!!

 

Thank you

 

Live masterclass