Generate Random Numbers with no repeats and maximum Sub-array Problem.. Kadane's algorith

Hi Guys, Can you please help me out on this.

I want to generate random numbers with no duplicates (including negative numbers) lets say from -20 til 20 in no particular order. And then I want to find the series of consectuive numbers within the randomly generated numbers that gives the maximum sum of values, locate the beginning of the series and the length of the series (number of values summed to get the maximum number).

For Example (-1, 2, -3, 3, 5)

- Sum = 8 (Sum of 3 and 5) we exclude 2 since it is not part of the consecutive numbers within the series because of -3 in the middle.
- Beginning location of the series = 4 (since 3 is the 4th number within the series).
- Length of the series within the series = 2 (Since 3 and 5 are the two consecutive integers within this series that would give the maximum sum of values).

I need the sum, beggining and the length of the series to be found through formuleas in excel if possible.

I have across a solution in the below link, but can someone do this using formulaes. I believe its called the kadane's algorithm.

http://www.i-programmer.info/program...y-problem.html

Kadane's algorithm, which is O(n), doesn't return the start and end indices, and it's not immediately obvious to me how to do so.

The alternative is a pair of nested loops in O(n^3) time.

Either way, I don't see any reasonable formula-based solution.

What is the urgent purpose of this?

	A	B	C	D	E	F
1	10
2	-5		Sum	Start	Stop
3	14		51	9	18	C3:E3: {=Kadane(A1:A20)}
4	7
5	-20
6	5
7	-11
8	-17
9	15
10	17
11	-2
12	-8
13	8
14	18
15	-14
16	1
17	-4
18	20
19	-3
20	-7

Please Login or Register  to view this content.

hey SHG,

Thanks a million, it worked i copied the whole code in vba in a module inserted by writing clicking the sheet then insert module and saved as excel macro enables workbook. generated the numbers and inserted the formulae {= kadane(range)}, and it showed me the max sum. However, i cant get the beg and stop to work. Sorry for not knowing how to get it to work and bothering you and thanks again.

Select all three cells, paste the formula in the formula bar, press and hold the Ctrl and Shift keys, then press Enter.

You're welcome.