Maximum Sum, by Amazon
Daily Coding Problem:
The solution is actually quite simple, but requires some thinking: you'll have two variables, one keeps track of the current sum, the other one the maximum sum.
The logic for the maximum sum is actually pretty simple, so we'll start with that:
max = Math.Max(current, max);
Straightforward right? Basically max will be the max between max and current.
Now for current, there are two options: if the current value plus current is positive, then sure, add it to current. Otherwise, set it to zero:
current = Math.Max(current + numbers[i], 0);
When you put it all together, the solution becomes the one below. Hope you enjoyed, thanks, Marcelo.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DailyCodingProblem
{
class DailyCodingProblem11022018
{
public int MaximunSum(int[] numbers)
{
int max = 0;
int current = 0;
for (int i = 0; i < numbers.Length; i++)
{
current = Math.Max(current + numbers[i], 0);
max = Math.Max(current, max);
}
return max;
}
}
}
This problem was asked by Amazon.
Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.
Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.
Do this in O(N) time.
The solution is actually quite simple, but requires some thinking: you'll have two variables, one keeps track of the current sum, the other one the maximum sum.
The logic for the maximum sum is actually pretty simple, so we'll start with that:
max = Math.Max(current, max);
Straightforward right? Basically max will be the max between max and current.
Now for current, there are two options: if the current value plus current is positive, then sure, add it to current. Otherwise, set it to zero:
current = Math.Max(current + numbers[i], 0);
When you put it all together, the solution becomes the one below. Hope you enjoyed, thanks, Marcelo.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DailyCodingProblem
{
class DailyCodingProblem11022018
{
public int MaximunSum(int[] numbers)
{
int max = 0;
int current = 0;
for (int i = 0; i < numbers.Length; i++)
{
current = Math.Max(current + numbers[i], 0);
max = Math.Max(current, max);
}
return max;
}
}
}
Comments
This was one of the problems I was asked during my first interview with Microsoft... It's a beautiful solution and fortunately also the one I've used :) Since then I've also learned that it's called Kadane's algorithm.
Reply DeletePost a Comment
[γγ¬γΌγ ]