Increasing sub-array

Computer Science Level 4

Given the following array of numbers , what is the number of sub-arrays(size greater than 1) that are strictly increasing?

As an explicit example, for the array $[3, 4, 3, 3, 7]$ , the number of contiguous sub-arrays that are strictly increasing is 2, namely [3, 4] and [3,7] .

The answer is 3657.

2 solutions

Arkajyoti Banerjee
Sep 27, 2017

#include <iostream>
#include <fstream>
using namespace std;
main()
{
  int N = 1, S = 0;
  char c;
  fstream fin("old.txt", ios :: in);    // contents of the text file have been copied (without moderation) to this text file
  fstream fout("new.txt", ios :: out);  // only the numbers will be copied to this text file
  while(true)
  {
    fin.get(c);
    if(fin.eof()) break;
    if(c != '[' && c != ']' && c != ',')  fout << c;
      else  if(c == ',') N++;
  }
  fout.close();
  fin.close();
  fin.open("new.txt", ios :: in);
  int a[N];
  for(int i = 0; i < N; i++) fin >> a[i];
  fin.close();
  for(int i = 0; i < N-1; i++)
    for(int j = i+1; a[j] > a[j-1]; j++)
        S++;
  cout << S;
}

Mehdi K.
May 22, 2016

Python3

>>> def NoISA(l):
...     arr = 0
...     i = 0
...     while i < len(l) - 1:
...         for j in range(i + 1, len(l)):
...             if l[j] <= l[j-1]:
...                 arr += 0.5 * (j - i - 1) * (j - i)
...                 i = j
...                 break
...         else:
...             arr += 0.5 * (j - i) * (j - i + 1) 
...             break
...     return int(arr)
... 
>>> NoISA(the_given_list)
3657

Nice solution, Mehdi. It would be great if you explained your algorithm in words too.

Pranshu Gaba - 5 years ago

Increasing sub-array

The answer is 3657.

2 solutions

0 pending reports