Understand Kadane's Algorithm Problem

Problem Name: Kadane's Algorithm

Problem Description:

Kadane's Algorithm

Objective: Find the contiguous subarray within a given array that has the maximum sum using Kadane's algorithm.

Problem Description

Kadane's algorithm is a dynamic programming approach that efficiently solves this problem in O(n) time, where n is the number of elements in the array.

Steps to Solve the Problem

1. Initialization:

Maintain two variables:
- max_ending_here: Stores the maximum sum of a contiguous subarray ending at the current index.
- max_so_far: Stores the overall maximum sum of a contiguous subarray found so far.
Both variables are initialized to the first element of the array.

2. Iteration:

Loop through the array starting from the second element (index 1).
At each index:
1. Check Current Element:
  - If the current element (arr[i]) is greater than max_ending_here + arr[i], start a new subarray from the current element:
    max_ending_here = arr[i].
  - Otherwise, extend the current subarray:
    max_ending_here = max_ending_here + arr[i].
2. Update Overall Maximum:
  - Compare max_ending_here with max_so_far.
  - If max_ending_here is larger, update max_so_far:
    max_so_far = max(max_so_far, max_ending_here).

3. Result:

After iterating through the entire array, max_so_far contains the maximum sum of a contiguous subarray.

Example

Input Array:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Iteration Breakdown:

Index 0: Element -2
- max_ending_here = -2
- max_so_far = -2
Index 1: Element 1
- max_ending_here = 1
- max_so_far = 1
Index 2: Element -3
- max_ending_here = -2
- max_so_far = 1
Index 3: Element 4
- max_ending_here = 4
- max_so_far = 4
Index 4: Element -1
- max_ending_here = 3
- max_so_far = 4
Index 5: Element 2
- max_ending_here = 5
- max_so_far = 5
Index 6: Element 1
- max_ending_here = 6
- max_so_far = 6
Index 7: Element -5
- max_ending_here = 1
- max_so_far = 6
Index 8: Element 4
- max_ending_here = 5
- max_so_far = 6

Final Result:

Maximum Sum of a Contiguous Subarray: 6

Key Insights

Kadane's algorithm uses a simple, iterative approach to track the maximum sum, making it efficient and elegant.
It dynamically adjusts whether to start a new subarray or continue the current one, based on which yields a higher sum.

Category:
Arrays

Programming Language:
Java

Reference Link:

https://leetcode.com/problems/maximum-subarray/description/

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

INPUT: [-2 , 1, -3 , 4, -1, 2 , 1, -5 ,4]

OUTPUT: 6

public static void main(String[] args) {

int[] arr = {2, 3, -8, 7, -1, 2, 3};

System.out.println(maxsubArraySum(arr));

}//function end

Helper Function:

static int maxsubArraySum(int[] arr) {

int res = arr[0];

for (int i = 0; i < arr.length; i++) {

int currSum = 0;

for (int j = i; j < arr.length; j++) {

currSum = currSum + arr[j];

res = Math.max(res, currSum);

}//Loop End

return res;