1
$\begingroup$

Given an integer array, I want to find the continuous subarray (containing at least one number) which has the largest sum. There are some algorithmic solutions to this here: https://en.wikipedia.org/wiki/Maximum_subarray_problem

However, I want to be able to eyeball a solution quickly (in about 5-10 seconds) given such an integer array of 10-15 elements (so not too many where it would be infeasible to eyeball in a short amount of time, but clearly greater than 2-3 elements), doing as little explicit pencil and paper calculation as possible.

Clearly humans are different from computers, so I was wondering if anyone had any insight/strategies/tricks as to how do so quickly by eyeballing in a situation with 10-15 elements?

Edit: To clarify, I am not looking to explicitly calculate the largest sum within 5-10 seconds, but rather I'm looking for the indices where the largest sum begins and ends.

$\endgroup$
2
  • $\begingroup$ "Clearly humans are different from computers" In my experience, the best algorithm for computers is usually pretty good for humans too. For example, I sort documents using MergeSort. Have you tried doing Kadane's algorithm by hand? $\endgroup$
    – Jacob Manaker
    Commented Sep 21, 2022 at 18:38
  • $\begingroup$ keyword: cumsum $\endgroup$
    – user619894
    Commented Sep 21, 2022 at 19:20

0

Reset to default

You must log in to answer this question.