A note on methodology
I thought a bit about this problem, and came to a solution. When I read Saeed Amiri's answer, I realized that what I came up with was a specialized version of the standard longest subsequence finding algorithm for a sequence of length 3. I'm posting the way I came up with the solution, because I think it is an interesting example of problem solving.
The two-element version
Let's start small: instead of looking for three indices at which the elements are in order, let's look for two: $i < j$ such that $A[i] < A[j]$.
If $A$ is decreasing (i.e. $\forall i < j, A[i] \ge A[j]$, or equivalently $\forall i, A[i] \ge A[i+1]$), then there are no such indices. Otherwise, there is an index $i$ such that $A[i] < A[i+1]$.
This case is very simple; we'll try to generalize it. It shows that the problem as stated is not solvable: the requested indices do not always exist. So we will rather ask that the algorithm either returns valid indices, if they exist, or correctly claims that no such indices exist.
Coming up with the algorithm
I will use the term subsequence to mean an extract from the array $A$ consisting of indices that may not be consecutive ($(A[i_1],\ldots,A[i_m])$ with $i_1 < \dots < i_m$), and run to mean consecutive elements of $A$ ($(A[i],A[i+1],\ldots,A[i+m-1])$).
We just saw that the requested indices do not always exist. Our strategy shall be to study when the indices do not exist. We'll do this by supposing we're attempting to find the indices and seeing how our search might go wrong. Then the cases where the search doesn't go wrong will provide an algorithm to find the indices.
With two indices, we could find consecutive indices. With three indices, we might not be able to come up with $j=i+1$ and $k=j+1$. However, we can consider the case when there is a run of three strictly increasing elements ($A[i] < A[i+1] < A[i+2]$) to be solved, as it is easy to recognize such runs, and see how this condition might not be met. Suppose that the sequence has no strictly increasing run of length 3.
The sequence only has strictly increasing runs of length 2 (which I'll call ordered pairs for short), separated by a decreasing run of length at least 2. In order for a strictly increasing run $A[j] < A[j+1]$ to be part of an increasing 3-element sequence, there must be an earlier element $i$ such that $A[i] < A[j]$ or a later element $k$ such that $A[j+1] < A[k]$.
A case when neither $i$ nor $k$ exists is when each ordered pair is entirely lower than the next one. This isn't all: when the pairs are interlaced, we need to compare them more finely.
The leftmost element $i$ of an increasing subsequence needs to come early and be small. The next element $j$ needs to be larger, but as small as possible to be able to find a third larger element $k$. The first element $i$ is not always the smallest element in the sequence, and it is not always the first for which there is a subsequent larger element, either — sometimes there is a lower 2-element subsequence further on, and sometimes there is a better fit for the already-found minimum.
Going from left to right, we tentatively pick the smallest element as $i$. If we find a larger element further right, we pick this pair as a tentative $(i,j)$. If we find an even larger $k$, we've won. The key thing to note is that our pick of $i$ and our pick of $(i,j)$ are updated independently: if we have a candidate $(i,j)$ and we find $i' > j$ such that $A[i'] < A[i]$, $i'$ becomes the next candidate $i$ but $(i,j)$ remains. Only if we find $j'$ such that $A[j'] < A[j]$ will $(i',j')$ become the new candidate pair.
Statement of the algorithm
Given in Python syntax, but beware that I haven't tested it.
"""Return the indices of a subsequence of length 3, or None if there is none."""
index1 = None; value1 = None
index2 = None; value2 = None
for i in range(0,len(A)):
if index1 == None or A[i] < value1:
index1 = i; value1 = A[i]
else if A[i] == value1: pass
else if index2 == None:
index2 = (index1, i); value2 = (value1, A[i])
else if A[i] < value2:
index2 = i; value2 = A[i]
else if A[i] > value2:
return (index2, index2, i)
index1 is the index of the minimum of the part of the array that has already been traversed (if it occurs several times, we retain the first occurrence), or
None before processing the first element.
index2 stores the indices of the increasing subsequence of length 2 in the already-traversed part of the array that has the lowest largest element, or
None if such a sequence doesn't exist.
return (index2, index2, i) runs, we have
value2 < value (this is an invariant of
value < A[i] (obvious from the context). If the loop ends without invoking the early return, either
value1 == None, in which case there is no increasing subsequence of length 2 let alone 3, or
value1 contains the increasing subsequence of length 2 that has the lowest largest element. In the latter case, we furthermore have the invariant that no increasing subsequence of length 3 ends earlier than
value1; therefore the last element of any such subsequence, added to
value2, would form an increasing subsequence of length 3: as we also have the invariant that
value2 is not part of an increasing subsequence of length 3 contained in the already-traversed part of the array, there is no such subsequence in the whole array.
Proving the aforementioned invariants is left as an exercise for the reader.
We use $O(1)$ additional memory, and traverse the array as a stream from left to right. We perform $O(1)$ processing for each element, leading to a run time of $O(n)$.
Left as an exercise to the reader.