algorithm thing

impl.cc

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

std::vector<unsigned> random_vec(const unsigned count) {
  std::random_device rnd_device;
  std::mt19937 mt(rnd_device());
  std::uniform_int_distribution<unsigned> dist;

  auto gen = [&]() { return dist(mt); };
  std::vector<unsigned> vec{count};
  std::generate(std::begin(vec), std::end(vec), gen);
  std::sort(std::begin(vec), std::end(vec));

  return vec;
}

std::pair<unsigned, unsigned> brute_force(std::vector<unsigned> const &v,
                                          const unsigned w) {
  unsigned max = 0;
  unsigned im = 0;
  unsigned jm = 0;

  for (unsigned i = 0; i < v.size(); ++i) {
    for (unsigned j = 1; j <= v.size(); ++j) {
      if (v[j - 1] - v[i] <= w) {
        if (j - i > max) {
          max = j - i;
          im = i;
          jm = j;
        }
      }
    }
  }

  return {im, jm};
}

std::pair<unsigned, unsigned> linear(std::vector<unsigned> const &v,
                                     const unsigned w) {
  for (unsigned i = 0, j = v.size();;) {
    if (v[j - 1] - v[i] <= w) {
      return {i, j};
    }

    const auto a = v[j - 2] - v[i];
    const auto b = v[j - 1] - v[i + 1];
    if (a < b) {
      --j;
    } else {
      ++i;
    }
  }
  __builtin_unreachable();
}

int main(int argc, char **argv) {
  std::random_device rnd_device;
  std::mt19937 mt(rnd_device());
  std::uniform_int_distribution<unsigned> dist{0, 199};

  for (unsigned k = 0; k < 1000; ++k) {
    const auto vec = random_vec(200);
    const auto w = dist(mt);
    const auto[bi, bj] = brute_force(vec, w);
    const auto[i, j] = linear(vec, w);

    std::cout << "w = " << w << std::endl;
    if (bi != i || bj != j) {
      std::cout << "Fail: (bi, bj) = (" << bi << ", " << bj << ") -- (i, j) = ("
                << i << ", " << j << ")" << std::endl;
    }
  }

  /*
  //test a specific case:
  const std::vector<unsigned> vec = {0,2,4,8,15,20,25,30,35,40};
  const auto w = 8;
  const auto[bi, bj] = brute_force(vec, w);
  const auto[i, j] = linear(vec, w);

  if (bi != i || bj != j) {
    std::cout << "Fail: (bi, bj) = (" << bi << ", " << bj << ") -- (i, j) = ("
              << i << ", " << j << ")" << std::endl;
  }
  */

  /*const std::vector<unsigned> vec = {0,2,4,6,10,15,16,17,18,19,20,21,25,30};
  const auto w = 6;
  const auto[bi, bj] = brute_force(vec, w);
  const auto[i, j] = linear(vec, w);

  if (bi != i || bj != j) {
    std::cout << "Fail: (bi, bj) = (" << bi << ", " << bj << ") -- (i, j) = ("
              << i << ", " << j << ")" << std::endl;
  }*/
}

notes.txt

1)
v = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
w = 5

i = 0 j = 10 -> v[9] - v[0] = 9
i = 1 j = 10 -> v[9] - v[1] = 8
i = 2 j = 10 -> v[9] - v[2] = 7
i = 3 j = 10 -> v[9] - v[3] = 6
i = 4 j = 10 -> v[9] - v[4] = 5 -> (i, j) = (4, 10) -> j - i = 6

i = 0 j = 10 -> v[9] - v[0] = 9
i = 0 j =  9 -> v[8] - v[0] = 8
i = 0 j =  8 -> v[7] - v[0] = 7
i = 0 j =  7 -> v[6] - v[0] = 6
i = 0 j =  6 -> v[5] - v[0] = 5 -> (i, j) = (0, 6) -> j - i = 6

==> for this case it doesn't matter

2)
v = [1, 4, 8, 20]
w = 10

i = 0 j = 4 -> v[3] - v[0] = 19
i = 1 j = 4 -> v[3] - v[1] = 16
i = 2 j = 4 -> v[3] - v[2] = 12
i = 3 j = 4 -> [v3] - v[3] = 0 -> (i, j) = (3, 4) -> j - i = 1

i = 0 j = 4 -> v[3] - v[0] = 19
i = 0 j = 3 -> v[2] - v[0] = 7 -> (i, j) = (0, 3) -> j - i = 3

3)
v = [1, 12, 16, 20]
w = 10

i = 0 j = 4 -> v[3] - v[0] = 19
i = 1 j = 4 -> v[3] - v[1] = 8 -> (i, j) = (1, 4) -> j - i = 3

i = 0 j = 4 -> v[3] - v[0] = 19
i = 0 j = 3 -> v[2] - v[0] = 15
i = 0 j = 2 -> v[1] - v[0] = 11
i = 0 j = 1 -> v[0] - v[0] = 0 -> (i, j) = (0, 1) -> j - i = 1


--> idea:
find in the sequence the first number that is >= w and name its index k

if k > size/2 {
    we decrement j
} else {
    we increment i
}

4)
v = [0, 2, 4, 8, 15, 20, 25, 30, 35, 40]
w = 8


v = [0, 2, 4, 6, 10, 15, 16, 17, 18, 19, 20, 21, 25, 30]
w = 6

i = 0 j = 14 -> v[13] - v[0] = 30 > 6
     ---        v[12] - v[0] = 25
     ---        v[13] - v[1] = 28
     --> decrement j
i = 0 j = 13 -> v[12] - v[0] = 25 > w
     ---        v[11] - v[0] = 21
     ---        v[12] - v[1] = 23
     --> decrement j
i = 0 j = 12 -> v[11] - v[0] = 21 > w
     ---        v[10] - v[0] = 20
     ---        v[11] - v[1] = 19
     --> increment i


v = [1, 12, 16, 20]
w = 10

i = 0 j = 4 -> v[3] - v[0] = 19
     ---       v[2] - v[0] = 15
     ---       v[3] - v[1] =  8
     --> incr i

question

The algorithm below try to find the maximal j-i possible if A[j - 1] - A[i] <= w 
(A being an already ordered vector and w being an argument to the function). 
This currently takes O(n^2), what would be the best way to have the same code taking only O(n) time complexity?

std::pair<unsigned int, unsigned int> forceBrute(const std::vector<unsigned int>& A, unsigned int w) {
  assert(!A.empty());

  unsigned int valeurMax = 0;
  unsigned int iMax = 0;
  unsigned int jMax = 0;

  for(unsigned int i = 0; i <= A.size(); i++)
    for(unsigned int j = 0; j < A.size(); j++)
      if(A[j - 1] - A[i] <= w)
        if (j - i > valeurMax) {
          valeurMax = j - i;
          iMax = i;
          jMax = j;

        }