Amazon Coding Interview Question - Maximum Sum Subarray

Maximum Sum Subarray Problem (Amazon, Microsoft & Linkedin Coding Interview Question). We analyze the problem, solve it with brute force, and then with Kadane's Algorithm.

Timestamps:
Introduction: 0:00
Problem: 0:30
Quadratic Solution: 4:34
Linear Solution: 7:44

If you find this useful please consider subscribing to the channel!

Find the code here:

Kadane's Algorithm blog post:

-------------------------------------------------------------------------------------------------------------

Tags
Maximum Sum Subarray
Coding Interview Question
Coding Exercise
Amazon coding interview Question
Microsoft coding interview question
Kadane's algorithm
Amazon Interview
Amazon Coding

[apoorvtyagi]

Kadane's algo was one the first algorithm that I learned & which blew my mind just because how easy it is to comprehend & how often I used it in many coding problems. It also has applications in Computer vision & ML too.

Great video Matt!

[naturebc]

int[] values = new int[10] { 2, 3, 56, -8, 0, 1, -3, 4, 5, 99 };
int MaxSum = int.MinValue;
int CurrentSum = 0;
for (int i = 0; i < values.Length; i++)
{
if (MaxSum == int.MinValue)
{
CurrentSum = values[i];
MaxSum = values[i];
}
else
{
if (values[i] > values[i - 1])
{
CurrentSum += values[i];
}
else
{
CurrentSum = values[i];
}
}

if (MaxSum < CurrentSum)
{
MaxSum = CurrentSum;
}
}