Hello there, if you are looking for Kadane’s Algorithm you must have come across the question: Largest sum contiguous subarray or Maximum Subarray Sum, by the way, both are the same.

(https://practice.geeksforgeeks.org/problems/kadanes-algorithm-1587115620/1)

This question can also be solved with brute force, which will give a time complexity of O(n^2), to improve this solution we will use kadane’s algorithm and which can be used to improve the time complexity.

## Brute Force approach to find Maximum Subarray Sum

Let’s take an example array:

In this example, the whole array sum is the maximum sum, i.e., 9

One very obvious but not-so-good solution is to calculate the sum of every possible subarray and the maximum of those would be the solution. We can start from index 0 and can calculate the sum of every possible subarray starting with A[0] as shown in the figure.

**Note:** Every element of the array is also a subarray.

### Code for Maximum Subarray Sum using Brute force approach:

long long maxSubarraySum(int arr[], int n){ int sum = INT_MIN; for(int i = 0;i<n;i++) { int s = 0; for(int j = i;j<n;j++) { s+= arr[j]; sum = max(sum, s); } } return sum; }

Here, we declare sum as global sum and s and local sum. The local sum is used to calculate the sum of every subarray and the global sum is used to calculate the max sum of all local sums.

For each element, we declare our local sum as 0 and keep adding later elements to the local sum, after adding each and every element we update our global sum with the max of the local sum.

The problem is this solution takes O(n^2). The array of very long-size computations will be very complex as the number of subarrays will increase rapidly.

## Kadane’s Algorithm

The optimized solution for the given problem is kadane’s algorithm.

What kadane’s algorithm actually says, every element has two choices:

- It can be a part of a subarray with the last elements or elements.
- It can start a new subarray including the element itself.

**How to decide which one to choose?**

We check if the sum before the element is less than the current element we start the new subarray with that element.

Let’s take the array shown above as an example.

We will traverse the array and will see how the algorithm works after that we will go through the code.

**For i = 0,**

We have no other element so our sum will be -5.

**For i = 1,**

arr[i] = 1,

**For 1,**

we have two choices either we consider -5 + 1 or only 1, as 1 > -5, we consider 1.

**For i = 2,**

arr[i] = -2

**For -2,**

we have choices -5 + 1 + -2, 1 + -2 and -2 among all these -1 is the greatest and if we look closely it is last greatest sum + arr[i].

**For i = 3,**

arr[i] = 3

We can have either -1 + 3 or only 3, 3 > 2, we will update our sum as 3.

Similarly going on we will find our greatest sum as 4.

### Code to find the Largest sum contiguous subarray or Maximum Subarray Sum using Kadane’s Algorithm:

long long maxSubarraySum(int arr[], int n){ int res = arr[0]; int maxEnding = arr[0]; for(int i=1;i<n;i++) { maxEnding = max(maxEnding + arr[i], arr[i]);//updating value of sum res = max(res, maxEnding);//updating largest value } return res; //returning value }

**Conclusion**

In this article, we learned how to solve the Maximum Subarray Sum in O(n) time complexity and also what is kadane’s algorithm and how it can make calculations very easy.

**Also Read:**

- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
- HackerRank Day 12 Solution in Python: Inheritance