[go: up one dir, main page]
Scribd
Upload
36 views3 pages

Kadane Algorithm TakeUForward Task

Kadane's Algorithm is a dynamic programming approach to find the maximum sum of a contiguous subarray in linear time. It involves iterating through an array while maintaining the current subarray sum and updating the overall maximum sum when necessary. The algorithm has a time complexity of O(n) and a space complexity of O(1).

Uploaded by

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

Kadane Algorithm TakeUForward Task

Kadane's Algorithm is a dynamic programming approach to find the maximum sum of a contiguous subarray in linear time. It involves iterating through an array while maintaining the current subarray sum and updating the overall maximum sum when necessary. The algorithm has a time complexity of O(n) and a space complexity of O(1).

Uploaded by

abhinaysandiri12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Kadane’s Algorithm – Finding the

Maximum Subarray Sum


1. Intuition – Real-life Analogy
Imagine you are walking along a street collecting coins and sometimes losing coins (positive
and negative values). Your goal is to walk through a section of this street where you collect
the maximum number of coins in one go—without skipping any positions in that stretch.

In programming terms, you are given an array of integers (both positive and negative), and
you must find a contiguous subarray (i.e., sequence of elements without breaks) that has the
maximum possible sum.

2. Approach – Step-by-Step Explanation


Kadane’s Algorithm solves the Maximum Subarray Problem using dynamic programming in
linear time:

1. Steps:

Initialize two variables:


- maxSum to store the overall maximum sum.
- currentSum to store the current subarray sum.

Iterate through the array:


- At each step, choose the maximum between the current element and currentSum + current
element.
- Update maxSum if currentSum is greater than maxSum.

Formula:
currentSum = max(currentElement, currentSum + currentElement)
maxSum = max(maxSum, currentSum)

3. Dry Run – Example with Diagram


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

Index Element currentSum maxSum

0 -2 -2 -2

1 1 1 1

2 -3 -2 1
3 4 4 4

4 -1 3 4

5 2 5 5

6 1 6 6

7 -5 1 6

8 4 5 6

Final Result: maxSum = 6 (from subarray [4, -1, 2, 1])

4. Code – In C++, Java, Python, JavaScript

C++

int maxSubArray(vector<int>& nums) {


int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}

Java

public int maxSubArray(int[] nums) {


int maxSum = nums[0], currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}

Python
def maxSubArray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum

JavaScript

function maxSubArray(nums) {
let maxSum = nums[0], currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}

5. Time & Space Complexity


Time Complexity: O(n) – Each element is visited once.

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

You might also like