0
$\begingroup$

Given array $A$ of $n$ real numbers. find in $O(n)$ time the sequence with the smallest sum. in other words to find the indexes $1\leqslant i\leqslant j \leqslant n$ that gives the minimum sum of $\sum\limits_{k=1}^{j}A[k]$.

For example: for the array $[2,-3,0,1,-4,7,-5]$ the sequence $[-3,0,1,-4]$ with sum $-6$ is the optimal sequence.

Attempt:

Let $S(j)$ be the sum of the optimal sequence that ends in the $j$-th cell. in the example: $$S(1)=2\\ S(2)=-3\\ S(3)=-3\\ S(4)=-2\\ S(5)=-6\\ S(6)=1\\ S(7)=-5$$

therefore:

$$S(j)=\begin{cases}0\qquad \qquad \qquad \qquad \qquad,j=0\\ \min\{A[j]+S(j-1),A[j]\}\quad ,j>0\end{cases}$$


for finding $i$ :

Let $i(j)$ be the index that the optimal sequence starts. in the given example:

$$i(1)=1\\ i(2)=2\\ i(3)=2\\ i(4)=2\\ i(5)=2\\ i(6)=2\\ i(7)=7$$

Need help on how to find $i$

$\endgroup$
1
  • $\begingroup$ Hint: consider the sequence of partial sums of the given array. What do you want to find in this sequence in order to solve the original problem? $\endgroup$
    – Gnuk
    Commented Jan 9, 2017 at 21:56

1 Answer 1

1
$\begingroup$

This is known as wikipedia : Maximum subarray problem

You can apply the Kadane's algorithm to the array -A [ ] (thus will find the minimum).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .