Maximizing number of factors contributing in the sum of sorted array bounded by a value - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:27:24Z http://mathoverflow.net/feeds/question/112284 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112284/maximizing-number-of-factors-contributing-in-the-sum-of-sorted-array-bounded-by-a Maximizing number of factors contributing in the sum of sorted array bounded by a value paramar 2012-11-13T13:51:33Z 2012-11-16T05:06:16Z <p>I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an <code>i&lt;A[n]</code> such that the sum of <code>|A[j:1 to n]-i|</code> is lesser than B and to that particular sum contribute the biggest number of A[j]s. I have some ideas but I can't seem to find anything better from the naive n*B and n*n algorithm. Any ideas about O(nlogn) or O(n) ? For example: Imagine</p> <blockquote> <p>A[n] = 1 2 10 10 12 14 and B&lt;7 then the best i is 12 cause I achieve having 4 A[j]s contribute to my sum. 10 and 11 are also equally good i's cause if i=10 I got 10 - 10 + 10 - 10 +12-10 + 14-10 = 6&lt;7</p> </blockquote> <p>These A[j]s must be contiguous. Because the problem is not trivial feel free to ask me if you find my descriptions ambiguous at some point</p> http://mathoverflow.net/questions/112284/maximizing-number-of-factors-contributing-in-the-sum-of-sorted-array-bounded-by-a/112302#112302 Answer by Tony Huynh for Maximizing number of factors contributing in the sum of sorted array bounded by a value Tony Huynh 2012-11-13T17:31:54Z 2012-11-13T17:40:49Z <p>It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid sequence with indices in <code>$\{1, \dots, t\}$</code> and the best valid sequence which ends with $A[t]$. At time $t+1$ we update $\mathbf{X}_t$ and $\mathbf{Y}_t$ as follows. If $(\mathbf{Y}_t, A[t+1])$ is a valid sequence of length longer than $\mathbf{X}_t$, then we set </p> <p><code>$\mathbf{X}_{t+1}:=(\mathbf{Y}_t, A[t+1])$</code> and <code>$\mathbf{Y}_{t+1}:=(\mathbf{Y}_t, A[t+1])$</code>.</p> <p>Otherwise, we set <code>$\mathbf{X}_{t+1}:=\mathbf{X}_t$</code> and we can compute $\mathbf{Y}_{t+1}$ in $O(\log (n))$-time via binary search. </p> http://mathoverflow.net/questions/112284/maximizing-number-of-factors-contributing-in-the-sum-of-sorted-array-bounded-by-a/112552#112552 Answer by fedja for Maximizing number of factors contributing in the sum of sorted array bounded by a value fedja 2012-11-16T05:06:16Z 2012-11-16T05:06:16Z <p>This seems to work, but you'd better check for idiotic mistakes :).</p> <pre><code>import math; srand(23); int N=60; int[] a; for(int k=0;k&lt;N;++k) a[k]=rand()%55; a=sort(a); int B=18; a[N]=a[N-1]+B+1; int K=0,k=0,m=0,s=0,S=0; while(true) { while((k+m&lt;N)&amp;&amp;(S&lt;=B)) { ++m; S+=a[k+m]-a[s]; s+=m%2; K=k; } if (k+m==N) {write(K,m-1); break;} else {++k; ++s; S+=a[k+m]-a[s-1]-a[s-m%2]+a[k-1];} } write(a); pause(); </code></pre>