# Kadane ‘s Algorithm in java

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

Kadane algorithm is a famous algorithm to solve maximum subarray problem.

### Maximum subArray problem:

From Wikipedia :
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Kadane ‘s Algorithm can be used to solve maximum sub array problem

• Initialize maxSoFar= 0 and maxEndingHere = 0
• Iterate over each element of the array
• maxEndingHere = maxEndingHere + a[i]
• if(maxEndingHere < 0)
•  maxEndingHere = 0
• if(maxSoFar < maxEndingHere)
•  maxSoFar = maxEndingHere
• return maxSoFar
Java Code:
Above algorithm won’t work if all elements of array are negative. We will make small changes to algorithm to make it work for negative numbers for too.

• Initialize maxSoFar= arr[0] and maxEndingHere = arr[0]
• Iterate over each element of the array
• maxEndingHere =Max of (arr[i], maxEndHere+arr[i])
• if(maxSoFar < maxEndingHere)
•  maxSoFar = maxEndingHere
• return maxSoFar
Java code:

When you run above program, you will get below output:

import_contacts

import_contacts

## Related Posts

• 18 June

### Maximum Number of Vowels in a Substring of Given Length

Table of ContentsApproach – 1 Generate All Substrings Using substring() MethodApproach – 2 Using Sliding Window Method (Linear Time Solution) In this article, we will look at an interesting problem related to the Strings and [Sliding-Window Algorithm](https://java2blog.com/sliding-window-maximum-java/ “Sliding-Window Algorithm”). The problem is : "Given a String we have to Find the Maximum Number of Vowel […]

• 04 June

### Search for a range Leetcode – Find first and last position of element in sorted array

Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

• 30 April

### Convert Postfix to Infix in Java

Learn about how to convert Postfix to Infix in java.

• 30 April

### Convert Prefix to Postfix in Java

Learn about how to convert Prefix to Postfix in java.

• 16 April

• 29 November

### Top 100+ Java coding interview questions

Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]