Given an array, the algorithm to find the maximum subarray sum is called Kadane’s Algorithm.The array can be of any dimension. For simplicity, let’s start with a 1D array. Let’s take a 0-indexed array: arr: [5, 7, -3, 2, 9, 6, 16, 22, 21, 29, -14, 10, 12] We can start the subarray at any point. Let’s say we start at index 2 i.e., arr[2] = -3. Now, at index 3, the sum will be -3 + 2 = -1. If we started the subarray at index 3 instead, the sum at index 3 is 2, which is greater than the previous sum. So we have two choices: either start at the current index or add the current element to the previous sum. And since we want the maximum subarray sum, we add the current element to the maximum of 0 and previous sum (zero here denotes that we’re starting anew from the current element). This problem falls under Dynamic Programming Paradigm. Let’s take an array dp[] where each dp[i] denotes maximum subarray sum ending at index i (including i). We can say that Base conditions: dp[0] = arr[0] Answer:A maximum element in the dp[] array Time Complexity: O(N)Space Complexity: O(N) We could optimize the space complexity by taking dp[i-1] which is the previous sum into a variable, eliminating the need for dp[] array. Time Complexity: O(N)Space Complexity: O(1) We could also find the indices of the subarray having the maximum sum. We could apply Kadane’s to 2D matrix as well, where we have to find the maximum submatrix sum. Feel free to try out kadane’s for 2D matrices. Thank you for reading! 😃

Manacher’s Algorithm Explained— Longest Palindromic Substring

Standing on the shoulders of giants

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

Kadane’s Algorithm Explained with Examples

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Binary Search In Detail

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Binary Search In Detail

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps