Maximum item in data stream I have N elements and need to find the maximum of these elements. At each time tick, exactly one of the N elements is updated and I need to determine the new max element (more specifically, the index of the max element). How can I do this by accessing as little "state" as possible?

The naive approach is to store all N elements and in each tick read the N elements and determine the max element. Here the amount of "state" accessed corresponds to N elements.

Is it possible to determine the max element by maintaining lesser state -- specifically state that grows sub-linearly as N increases? Essentially I do not want to make a pass on the entire set of N elements. Assume N is a fixed number.

It seems like this problem has the flavor of data streaming algorithms like the count(-min) sketch. We have N buckets -- items being streamed in update the count of one of these N buckets -- and wish to perform some query on these N buckets with sub-linear space usage. 

I understand how sketches can be used to query the value of the Nth bucket, but do not understand if it can be extended to obtain an estimate for the max value (and specifically, the index of the max element). The heavy hitters problem outputs items above a certain frequency, but I am interested only in the item with the maximum frequency. 

Am I over-thinking this problem? Is there a far simpler solution?
In the streaming model, any constant approximation of the maximum requires $\Omega(N)$ space. Showing this for a small enough constant approximation follows by an easy reduction from the disjointness problem in two-party communication complexity. This is now very standard, but I will describe it below anyways.

Recall that in the disjointness problem Alice is given a binary string $x \in \{0, 1\}^N$, and Bob is given a string $y \in \{0, 1\}^N$, and they want to decide whether $x$ and $y$ have disjoint support. It is a classic result that this task requires that Alice and Bob exchange at least $\Omega(N)$ bits, even if they share random bits and only want to succeed with probability $2/3$ over the choice of randomness. 

Assume there is a randomized streaming algorithm $A$ with space complexity $S$, which with probability $2/3$ computes a number $a$ such that $\frac{a}{F_\infty} \in (\frac{2}{3}, \frac{4}{3})$, where $F_\infty$ is the true maximum frequency of the $N$ elements. This gives a protocol for the disjointness problem with $S$ bits of communication, and therefore $S = \Omega(N)$. In the reduction, Alice simulates the algorithm $A$ and feeds it a stream which increases the frequency of element $i$ by $1$ for each $i$ such that $x_i = 1$. Then Alice takes the memory state of $A$ (which has only $S$ bits) and sends it to Bob, who then simulates $A$ starting from the state he received from Alice and feeds it a stream which increases the frequency of $i$ by $1$ for each $i$ s.t. $y_i = 1$. Then Bob decides that $x$ and $y$ have disjoint support if the output $a$ of $A$ is at most $4/3$. 

For more information, see Alon, Matias, and Szegedy's beautiful paper, which introduced the streaming model and proved the first lower bounds.