title: Divide array into smaller consecutive parts such that NEO value is maximal
body: <p>On this years <a href="http://www.bubblecup.org/" rel="nofollow noreferrer">Bubble Cup</a> (finished) there was the problem <a href="http://www.spoj.com/problems/NEO2/" rel="nofollow noreferrer">NEO</a> (which I couldn't solve), which asks </p>
  
  <p>Given array with n integer elements. We divide it into several part (may be 1), each part is a consecutive of elements. The NEO value in that case is computed by: Sum of value of each part. Value of a part is sum all elements in this part multiple by its length.</p>
  
  <p>Example: We have array: [ 2 3 -2 1 ]. If we divide it like: [2 3] [-2 1]. Then NEO = (2 + 3) * 2 + (-2 + 1) * 2 = 10 - 2 = 8.</p>
  
  <p>The number of elements in array is smaller then <code>10^5</code> and the numbers are integers between <code>-10^6</code> and <code>10^6</code></p>
  
  <p>I've tried something like divide and conquer to constantly split array into two parts if it increases the maximal NEO number otherwise return the NEO of the whole array. But unfortunately the algorithm has worst case O(N^2) complexity (my implementation is below) so I'm wondering whether there is a better solution </p>
  
  <p>EDIT: My algorithm (greedy) doesn't work, taking for example <code>[1,2,-6,2,1]</code> my algorithm returns the whole array while to get the maximal NEO value is to take parts <code>[1,2],[-6],[2,1]</code> which gives NEO value of <code>(1+2)*2+(-6)+(1+2)*2=6</code> </p>
  
  <pre><code>#include &lt;iostream&gt;
  int maxInterval(long long int suma[],int first,int N)
  {
      long long int max = -1000000000000000000LL; 
      long long int curr;
      if(first==N) return 0;
      int k;
      for(int i=first;i&lt;N;i++)
      {
          if(first&gt;0) curr = (suma[i]-suma[first-1])*(i-first+1)+(suma[N-1]-suma[i])*(N-1-i); // Split the array into elements from [first..i] and [i+1..N-1] store the corresponding NEO value
          else curr = suma[i]*(i-first+1)+(suma[N-1]-suma[i])*(N-1-i); // Same excpet that here first = 0 so suma[first-1] doesn't exist
          if(curr &gt; max) max = curr,k=i; // find the maximal NEO value for splitting into two parts
      }
      if(k==N-1) return max; // If the max when we take the whole array then return the NEO value of the whole array
      else
      {
          return maxInterval(suma,first,k+1)+maxInterval(suma,k+1,N); // Split the 2 parts further if needed and return it's sum
      }
  }
  int main() {
      int T;
      std::cin &gt;&gt; T;
      for(int j=0;j&lt;T;j++) // Iterate over all the test cases
      {
          int N;
          long long int NEO[100010]; // Values, could be long int but just to be safe
          long long int suma[100010]; // sum[i] = sum of NEO values from NEO[0] to NEO[i]
          long long int sum=0;
          int k;
          std::cin &gt;&gt; N;
          for(int i=0;i&lt;N;i++)
          {
              std::cin &gt;&gt; NEO[i];
              sum+=NEO[i];
              suma[i] = sum;
          }
          std::cout &lt;&lt; maxInterval(suma,0,N) &lt;&lt; std::endl;
      }
      return 0;
  }
  </code></pre>