Java Advanced Topics and Techniques

# Kadane's Algorithm with Java

## Introduction

Kadane’s Algorithm is used to find the subarray with the largest sum in the given array. The intuition behind this algorithm is to declare a variable ‘sum’ and keep adding the elements in the sum. And, each time you add an element to the sum, update it using the ‘max’ function.

It means that each time, the current sum and previous sum are compared. The sum is assigned the maximum value out of the previous sum and the current sum. Also, if the array contains negative elements then the sum is assigned 0. This is because if (-8) + (-7) is a case then the sum is -15 which should not be included.

## Algorithm

The algorithm for Kadane’s Algorithm is as follows:

- Initialize prevSum to 0, initialize currentSum to the minimum value of a 32-bit Integer
- Add array element in the prevSum
- Check if prevSum>currentSum:

- If true, then the sum is greater thus, assign prevSum to currentSum(the answer variable )
- If false, then no change in currentSum

4. If the prevSum was less than 0 then prevSum=0 because if the negative number is included then the sum is negative. In the next iteration, if a positive number is added to the sum (which is negative ), the overall sum is reduced.

Example: if prevSum=-4 and current element is 5 then sum = -4 + 5 = 1 which is less than the sum by including only the current element which is 5.

## Code Implementation

Below is the Java code for Kadane’s Algorithm to find the maximum sum Subarray:

Suppose the given array is: [-2,1,-3,4,-1,2,1,-5,4]. Here the maximum sum subarray is [,4,-1,2,1] with the sum as 6. Therefore, we declare two variables prevSum and currentSum. currentSum will store the actual answer and prevSum stores the sum of the elements in each iteration. The following observations are made:

## Iterations

**Iteration 1**

*prevSum= -2*

*prevSum>currentSum, thus currentSum=-2*

*prevSum<0 thus, prevSum=0*

**Iteration 2**

*prevSum= 1*

*prevSum>currentSum(-2) thus, currentSum=1*

*prevSum<0 is false thus prevSum=1*

**Iteration 3**

*prevSum= 1+ (-3)= -2*

*prevSum>currentSum is false thus currentSum=1*

*prevSum<0 thus prevSum=0*

**Iteration 4**

*prevSum=4*

*prevSum>currentSum thus currentSum=4*

*prevSum<0 is false thus prevSum=4*

**Iteration 5**

*prevSum= 4+ (-1)=3*

*prevSum>currentSum is false thus currentSum=4*

*prevSum<0 is false thus prevSum=3*

**Iteration 6**

*prevSum= 3+2 = 5*

*prevSum>currentSum thus currentSum=5*

*prevSum<0 is false thus prevSum=5 *

**Iteration 7**

*prevSum= 5+1 = 6*

*prevSum>currentSum thus currentSum=6*

*prevSum<0 is false thus prevSum = 6 *

**Iteration 8**

*prevSum= 6+ (-5)= 1*

*prevSum>currentSum is false thus currentSum=6*

*prevSum<0 is false thus prevSum = 1*

**Iteration 9**

*prevSum= 1+4= 5*

*prevSum>currentSum is false thus currentSum=6*

*prevSum<0 is false thus prevSum = 4 *

Therefore, the answer was stored in the currentSum which is returned in the end. Thus, the maximum sum of a subarray can be found using Kadane’s Algorithm.

Sample Output for the above code is: