A night out after long :)

So found the following question here (Antonio is awesum ) and worked out a O(n) time solution BUT with O(n) space. I claim the space usage can be brought down to O(1). Anyone game enough to post the O(1) space version?

Problem:

Given an array A of numbers, find a pair of numbers A[i] and A[j], such that A[i] < A[j] and j-i is maximized.

O(n) time O(n) space code

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  vector<int> numbers;
  int n;
  cin >> n;
  numbers.resize(n);
  for (int i = 0, t; i < n; ++i) {
    cin >> t;
    numbers[i] = t;
  }
  vector<pair<int, int> > decr;
  decr.push_back(make_pair(numbers[0], 0));
  for (int i = 1; i < numbers.size(); ++i) {
    if (numbers[i] < decr.back().first) {
      decr.push_back(make_pair(numbers[i], i));
    }
  }
  vector<pair<int, int> > incr;
  incr.push_back(make_pair(numbers[n-1], n-1));
  for (int i = n - 2; i >= 0; --i) {
    if (numbers[i] > incr.back().first) {
      incr.push_back(make_pair(numbers[i], i));
    }
  }
  reverse(incr.begin(), incr.end());
  int iter = min(incr.size(), decr.size());
  int max_diff = -1, s_i = -1, s_j = -1;
  int i_i = 0, d_i = 0;
  for (; i_i < incr.size() && d_i < decr.size();) {
    if (incr[i_i].first > decr[d_i].first) {
      int tmp_diff = incr[i_i].second - decr[d_i].second;
      if (tmp_diff > max_diff) {
        max_diff = tmp_diff;
        s_i = decr[d_i].second;
        s_j = incr[i_i].second;
      }
      i_i++;
    } else if (incr[i_i].first < decr[d_i].first) {
      d_i++;
    } else {
      i_i++;
      d_i++;
    }
  }
  cout << "i: " << s_i << "  j: " << s_j << endl;
  return 0;
}

जाग तुझको दूर जाना!

An awesome composition by a Hindi poet, महादेवी वर्मा

चिर सजग आँखें उनींदी आज कैसा व्यस्त बाना!
जाग तुझको दूर जाना!

अचल हिमगिरि के हॄदय में आज चाहे कम्प हो ले!
या प्रलय के आँसुओं में मौन अलसित व्योम रो ले;
आज पी आलोक को ड़ोले तिमिर की घोर छाया
जाग या विद्युत शिखाओं में निठुर तूफान बोले!
पर तुझे है नाश पथ पर चिन्ह अपने छोड़ आना!
जाग तुझको दूर जाना!

बाँध लेंगे क्या तुझे यह मोम के बंधन सजीले?
पंथ की बाधा बनेंगे तितलियों के पर रंगीले?
विश्व का क्रंदन भुला देगी मधुप की मधुर गुनगुन,
क्या डुबो देंगे तुझे यह फूल दे दल ओस गीले?
तू न अपनी छाँह को अपने लिये कारा बनाना!
जाग तुझको दूर जाना!

वज्र का उर एक छोटे अश्रु कण में धो गलाया,
दे किसे जीवन-सुधा दो घँट मदिरा माँग लाया!
सो गई आँधी मलय की बात का उपधान ले क्या?
विश्व का अभिशाप क्या अब नींद बनकर पास आया?
अमरता सुत चाहता क्यों मृत्यु को उर में बसाना?
जाग तुझको दूर जाना!

कह न ठंढी साँस में अब भूल वह जलती कहानी,
आग हो उर में तभी दृग में सजेगा आज पानी;
हार भी तेरी बनेगी माननी जय की पताका,
राख क्षणिक पतंग की है अमर दीपक की निशानी!
है तुझे अंगार-शय्या पर मृदुल कलियां बिछाना!
जाग तुझको दूर जाना!

More compositions of महादेवी वर्मा can be found here