# Kadane’s Algorithm: Find the maximum subarray sum in an array.

In this article, we will discuss Kadanes algorithm, a simple and efficient algorithm for finding the maximum subarray sum in an array. Kadane’s algorithm is a dynamic programming algorithm, which means that it breaks the problem down into smaller subproblems and solves them recursively.

Kadane’s algorithm works by maintaining two variables: a running sum and a maximum sum. The running sum starts at 0, and the maximum sum is initialized to the smallest possible value. As we iterate through the array, we add the current element to the running sum. If the running sum is negative, we reset it to 0. If the running sum is greater than the maximum sum, we update the maximum sum. At the end of the loop, the maximum sum will contain the maximum subarray sum.

```Example 1:

Input: arr = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Examples 2:

Input: arr = 

Output: 1

Explanation: Array has only one element and which is giving positive sum of 1.```

## Pseudocode

Time and space complexity

The time complexity of Kadane’s algorithm is O(n), where n is the length of the array. This is because the algorithm iterates through the array once, and each iteration takes constant time. The space complexity of Kadane’s algorithm is O(1), as it only uses two variables to store the running sum and the maximum sum.

### Practical Applications in Problem-Solving

Kadane’s algorithm can be used to solve a variety of problems, including:

• Finding the maximum subarray sum in an array
• Finding the maximum product subarray in an array
• Finding the maximum contiguous increasing subsequence in an array
• Finding the maximum contiguous decreasing subsequence in an array

Kadanes algorithm in Java for beginners

``````public class Kadane {

public static int kadane(int[] array) {
int runningSum = 0;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
runningSum = Math.max(runningSum + array[i], array[i]);
maxSum = Math.max(maxSum, runningSum);
}
return maxSum;
}

public static void main(String[] args) {
int[] array = {-2, -3, 4, -1, -2, 1, 5, -3};
}
}
``````

Powerful Tool in Competitive Programming

Kadane’s algorithm is a popular algorithm in competitive programming, as it is a simple and efficient way to solve a variety of problems. The algorithm is also relatively easy to implement, which makes it a good choice for beginners.

Kadane’s algorithm is a common interview question for software engineers, as it is a good way to assess a candidate’s knowledge of dynamic programming. The algorithm is also relatively easy to explain, which makes it a good choice for whiteboard interviews.

Conclusion

Kadanes algorithm is a simple and efficient algorithm for finding the maximum subarray sum in an array. The algorithm is easy to understand and implement, and it is a popular choice for competitive programming and interview questions.

#### Decoding the Future: Emerging Technologies in Various Engineering Branches

##### 2 thoughts on “Kadane’s Algorithm: Find the maximum subarray sum in an array.”
1. […] Technologies Shaping India’s Engineering Landscape Stock Buy and Sell Problem with Java Kadane’s Algorithm: Find the maximum subarray sum in an array. Mastering Pair Sum Problems: Tips and Tricks to Ace Coding Interview Challenges Unveiling […]

2. […] Technologies Shaping India’s Engineering Landscape Stock Buy and Sell Problem with Java Kadane’s Algorithm: Find the maximum subarray sum in an array. Mastering Pair Sum Problems: Tips and Tricks to Ace Coding Interview […]