Kadane's Algorithms for FAANG interviews

Let's talk about the most popular and most asked interview questions.

👉 𝐅𝐢𝐧𝐝 𝐭𝐡𝐞 𝐦𝐚𝐱𝐢𝐦𝐮𝐦 𝐬𝐮𝐦 𝐨𝐟 𝐚 𝐜𝐨𝐧𝐭𝐢𝐠𝐮𝐨𝐮𝐬 𝐬𝐮𝐛𝐚𝐫𝐫𝐚𝐲.

So how do you solve this question? 🤔
So many approaches are there, but the most popular approach is
using K̳a̳d̳a̳n̳e̳’̳s̳ ̳a̳l̳g̳o̳r̳i̳t̳h̳m̳

𝑺𝒐 𝒘𝒉𝒂𝒕 𝒊𝒔 𝑲𝒂𝒅𝒂𝒏𝒆’𝒔 𝒂𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎🤔?

👉 Kadane's algorithm is used to find the maximum sum of a contiguous subarray within an o̳n̳e̳-̳d̳i̳m̳e̳n̳s̳i̳o̳n̳a̳l̳ ̳a̳r̳r̳a̳y̳ ̳o̳f̳ ̳n̳u̳m̳b̳e̳r̳s̳, which is especially useful in financial or stock market analysis, weather data processing, and similar scenarios where trends or streaks need to be identified.

👉 𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 𝑺𝒕𝒆𝒑𝒔:

1. Initialize two variables:
- currentSum to track the ongoing sum of the subarray.
- maxSum to keep the maximum value found.

2. Iterate through the array:
- For each element, decide whether to add it to currentSum or start fresh with the current element (whichever is larger).
- Update maxSum if currentSum becomes greater than maxSum.
3. Return maxSum after processing all elements.

𝐋𝐞𝐭'𝐬 𝐝𝐢𝐬𝐜𝐮𝐬𝐬 𝐭𝐡𝐞 𝐩𝐬𝐞𝐮𝐝𝐨𝐜𝐨𝐝𝐞 (𝐲𝐨𝐮 𝐡𝐚𝐯𝐞 𝐭𝐨 𝐤𝐧𝐨𝐰 𝐡𝐨𝐰 𝐭𝐨 𝐰𝐫𝐢𝐭𝐞 𝐩𝐬𝐞𝐮𝐝𝐨𝐜𝐨𝐝𝐞 𝐚𝐬 𝐭𝐡𝐞 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰𝐞𝐫 𝐚𝐬𝐤𝐞𝐝 𝐲𝐨𝐮 𝐭𝐨 𝐰𝐫𝐢𝐭𝐞 𝐩𝐬𝐞𝐮𝐝𝐨𝐜𝐨𝐝𝐞).

function kadaneAlgorithm(array):

Here’s the pseudocode for Kadane's Algorithm to find the maximum sum of a contiguous subarray:

Kadane’s Algorithm Pseudocode

function kadaneAlgorithm(array):
    # Initialize variables
    maxSum = array[0]          # Start with the first element as max sum
    currentSum = array[0]       # Start with the first element as current sum

    # Iterate over the array starting from the second element
    for i from 1 to length(array) - 1:
        # Update currentSum by choosing the maximum between the current element 
        # or the current element added to currentSum
        currentSum = max(array[i], currentSum + array[i])

        # Update maxSum if currentSum is greater
        maxSum = max(maxSum, currentSum)

    return maxSum

𝐋𝐞𝐞𝐭𝐜𝐨𝐝𝐞 𝐩𝐫𝐨𝐛𝐥𝐞𝐦𝐬:

- https://lnkd.in/gxZn4vBM
- https://lnkd.in/gqSFpNEp
- Maximum difference of 0's and 1's in a binary string
- Maximum Sum Circular array
- Smallest sum contiguous subarray
- Largest sum increasing contiguous subarray
- Maximum Product Subarray
- Largest sum contiguous subarray with only non-negative elements.
- Largest sum contiguous subarray with unique elements.
- Maximum Alternating Sum Subarray
- Maximum Sum Rectangle In A 2D Matrix

𝑹𝒆𝒂𝒍 𝒘𝒐𝒓𝒍𝒅 𝒆𝒙𝒂𝒎𝒑𝒍𝒆 𝒔𝒄𝒆𝒏𝒂𝒓𝒊𝒐:

Imagine tracking daily temperature changes in a city for a month. Kadane’s algorithm could help you identify the warmest streak of consecutive days.

I̳ ̳h̳o̳p̳e̳ ̳y̳o̳u̳ ̳l̳i̳k̳e̳ ̳t̳h̳e̳ ̳e̳x̳p̳l̳a̳n̳a̳t̳i̳o̳n̳ ̳a̳n̳d̳ ̳u̳n̳d̳e̳r̳s̳t̳a̳n̳d̳i̳n̳g̳ ̳o̳f̳ ̳A̳l̳g̳o̳r̳i̳t̳h̳m̳s̳
̳
̳F̳o̳l̳l̳o̳w̳ ̳a̳n̳d̳ ̳c̳o̳n̳n̳e̳c̳t̳ ̳f̳o̳r̳ ̳m̳o̳r̳e̳ ̳c̳o̳d̳i̳n̳g̳ ̳a̳n̳d̳ ̳W̳e̳b̳ ̳d̳e̳v̳e̳l̳o̳p̳m̳e̳n̳t̳ ̳p̳o̳s̳t̳s̳ ̳ Ravi Kumar