The Beautiful sequence

Red Bull Rampage, Virgin, Utah, 2012
Rider: Brandon Semenuk, Photographer: Christian Pondella
Quite spectacular. The only connection between this photograph and my post is the title.

I've come to realize that solving programming puzzles is, for me, akin to solving crossword puzzles for people like Jack, i.e. people who like doing crossword puzzles. It's mental exercise, but I'm not sure there is any value in it. Actually, there is no value in it: the puzzle has already been solved. It does separate those who can muster the logic and reason needed to solve it and those who don't give a fig. I'm not sure that distinction has any value either.

Anyway, I picked up a puzzle yesterday and started looking at it. Here is a description of the problem.

We define the beautiful value of an integer sequence as the product of the value of its smallest element and its length. You are given an integer sequence containing Nelements, and you should find out one of its continuous subsequences, such that it has the largest beautiful value among all the continuous subsequences.
Please solve this problem with an O(N) algorithm.

So the simple way to solve this is to read all the numbers into an array, then pick a number and scan up and down the array until you find a value that is smaller. Now you know the range (a continuous subsequence) and when you multiply that by the number, you get the beautiful value for that number. Repeat this for all the numbers in the array and eventually you will have the biggest beautiful value.

The problem comes with the last line of the description:

Please solve this problem with an O(N) algorithm.

What this means is you can use as many steps you want to find the beautiful value for a number, but it has to be a fixed number of steps. It can't depend on how many numbers are in the array. For instance, if it takes you 100 steps to find the bv for a number, then it won't take more than 100 x N steps to find the largest one. The simple solution I set out above is going to take more like N squared steps, which is definitely not an O(N) class algorithm.

This morning I am climbing stairs as I try to do every day in order to get some exercise. Normally this can be a bit of a chore. The first few minutes go by easy enough, but once I get past the ten minute mark I am looking for the end. Today, though, I was thinking about this problem while I was climbing and when the timer went off it caught me unaware. I was so surprised that at first I suspected I had entered the wrong amount of time, like two minutes instead of twenty, but that wasn't the case.

Nothing like getting wrapped up in a problem to make time become meaningless. This might be why it is so difficult to determine how long it is going to take to write a computer program. You ask a programmer how long it will take to do something, and you get some answer, but then he/she goes off and starts working on it and if they get absorbed in a problem it may be months or even years before they come up for air.

Update Saturday, January 14, 2017. Took me a couple of days to figure out that I need to use a binary search algorithm to determine the range for each number, and then a couple more days to realize that the index into the sorted array is not the same as the original index, and then an hour or so more of fiddling around to get it straight in my head when to use the sorted indices and when to use the original indices. The binary search means the algorithm is an O(log N), but since we also need to process all of the elements, and the whole list needs to be sorted, I'm going to call it O(N x log N). I think this might be as good as you can get.