Scribd
Upload
7 views11 pages

Maximum Subarray Sum with Kadane's Algorithm

The document discusses the Maximum Subarray Problem and introduces Kadane’s Algorithm for finding the contiguous subarray with the largest sum. It outlines the algorithm's steps, provides a Java implementation, and analyzes its time and space complexity. The session aims to equip students with the ability to solve the problem and apply the algorithm in coding and interview scenarios.

Uploaded by

atulpalstudy12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
7 views11 pages

Maximum Subarray Sum with Kadane's Algorithm

The document discusses the Maximum Subarray Problem and introduces Kadane’s Algorithm for finding the contiguous subarray with the largest sum. It outlines the algorithm's steps, provides a Java implementation, and analyzes its time and space complexity. The session aims to equip students with the ability to solve the problem and apply the algorithm in coding and interview scenarios.

Uploaded by

atulpalstudy12
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

To Find Contiguous Subarray

with Maximum Sum

Session No.:
Course Name: Advanced Data Structures and Algorithms
Course Code: R1UC601B
Instructor Name: Dr. Mili Dhar
Duration: 50 mins
Date of Conduction of Class:

Galgotias University 1
Review of the key concepts of the previous session

Galgotias University 2
At the end of this session students will be able to

Learning Outcome 1: Learn the concept of the


Maximum Subarray Problem and implement
Kadane’s Algorithm.

Learning Outcome 2: Analyze its time and space


complexity. Apply the concept in coding and
interview problems.

Galgotias University 3
1. Introduction
2. Structure & Characteristics
3. Advantages & Disadvantages
Session [Link]-World Applications
Outline 5. Summary & Recap

Galgotias University 4
Problem Statement
Find the contiguous subarray within a one-dimensional array of numbers which
has the largest sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has the maximum sum = 6.

Galgotias University 5
Concept: Kadane’s Algorithm

• Iterate through the array, calculating the current sum at each index.
• Decide whether to start a new subarray or extend the previous one.
• Keep track of the maximum sum encountered so far.

Algorithm Steps
1. Initialize:
max_so_far = arr[0]
current_sum = arr[0]
2. For each element from index 1 to n-1:
current_sum = max(arr[i], current_sum + arr[i])
max_so_far = max(max_so_far, current_sum)
3. Return max_so_far

Galgotias University 6
Java Implementation
public static int maxSubArray(int[] nums)
{
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < [Link]; i++)
{
currentSum = [Link](nums[i], currentSum + nums[i]);
maxSum = [Link](maxSum, currentSum);
}
return maxSum;
} Dry Run Example:
Array: [-2,1,-3,4,-1,2,1,-5,4]
Step-by-step tracking of current_sum and max_sum.
Maximum Subarray Found: [4, -1, 2, 1] → Sum = 6

Galgotias University 7
Complexity Analysis

• Time Complexity: O(n) – Only one traversal required.


• Space Complexity: O(1) – Constant extra space used.

Galgotias University 8
Activity 1: Problem based

Write a Java program to find both the maximum


subarray sum and the subarray elements.
Test with: arr = [5, -2, 3, 4, -1, 2, -1, 2, -3, 4]

Galgotias University 9
Summary

✔ Kadane’s Algorithm efficiently finds maximum sum of


contiguous subarray.
✔ Works in linear time with constant space.
✔ Commonly asked in technical interviews.

Galgotias University 10
At the end of this session students will be able to

Learning Outcome 1: Solve Maximum Subarray


Problem and can implement Kadane’s
Algorithm.

Learning Outcome 2: Analyze its time and space


complexity. Apply the concept in coding and
interview problems.

Galgotias University 11

You might also like