Menu
Here's an interview questions that a colleague asked for a programming position. I thought this was great for watching the interviewee think it through. I'd love to get responses for how the SO community thinks of it.
Given a list of real numbers of length N, say [a_1, a_2, ..., a_N], what is the complexity of finding the maximum value M for which there exist indices 1 <= i <= j <= N such that
a_i + a_{i+1} + ... + a_j = M?
My apologies if this is a classic CS problem.
284
Simple Approach: Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.
The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with some point on right of mid + 1. Finally, combine the two and return the maximum among left, right and combination of both.
What is Kadane's Algorithm? Kadane's algorithm is an iterative dynamic programming algorithm in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.
The complexity is just O(n) for Kadane's algorithm:
The algorithm keeps track of the tentative maximum subsequence in
(maxSum, maxStartIndex, maxEndIndex). It accumulates a partial sum incurrentMaxSumand updates the optimal range when this partial sum becomes larger thanmaxSum.
189
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
