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