title: spoj ARRAYSUB: O(n) Complexity Approach
body: <p>I was trying to solve this problems on spoj 
  <a href="http://spoj.pl/problems/ARRAYSUB" rel="nofollow">http://spoj.pl/problems/ARRAYSUB</a></p>
  
  <p>I solved it using two approaches</p>
  
  <p>firstly  using optimised brute force.
  Secondly taking Pivot at k,2k,3k so on and finding maximum.</p>
  
  <p>Although both Solutions are accepted in worst case there Complexity are O(n*k);</p>
  
  <p><strong>Can anyone Suggest  O(n) solution Approach for the problems .</strong></p>
  
  <p>Below is my Running  Accepted code of worst case complexity O(n*k):</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;cstdio&gt;
  #include&lt;climits&gt;
  using namespace std;
  main()
  {
      long n;
      cin &gt;&gt; n;
      long *arr = new  long[n];
      for( long i=0;i&lt;n;i++)
          cin &gt;&gt; arr[i];
       long k;
      cin &gt;&gt; k;
       long max=arr[0];
      for(long i=1;i&lt;k;i++)
      {
          if(arr[i]&gt;max)
              max=arr[i];
      }
      if(k!=n)
      cout&lt;&lt;max&lt;&lt;" ";
      else cout&lt;&lt;max;
      for( long i=k;i&lt;n;i++)
      {
          if(arr[i-k]==max)
          {max=-1;
          for(int j=i-k+1;j&lt;=i;j++)
          if(arr[j]&gt;max)
          max=arr[j];
          if(i!=n)
          cout&lt;&lt;max&lt;&lt;" ";
          else cout&lt;&lt;max;
  
          }
          else{
          if(arr[i]&gt;max)
          {   max=arr[i];
  
          if(i!=n)
          cout&lt;&lt;max&lt;&lt;" ";
          else 
          cout&lt;&lt;max;
          }
          else
          {
          if(i!=n)
          cout&lt;&lt;max&lt;&lt;" ";
          else cout&lt;&lt;max;}
          }
      }
  
          cout&lt;&lt;endl;
      return(0);
  }
  </code></pre>