1. Technology

Programming Challenge 64 - Sum Some Sub-Array

Starts November 1st- Completed

By

This is a speed programming challenge. You are given a 1000 (signed) int elements array called numbers. This month's task is to find the largest sub array with the highest +ve total value. As there are a thousand elements the array index goes from 0..999 but you have to find the highest totalling sub-array.

A sub array is any contiguous array which starts at index s and finishes at element e where s >= 0 and s < e and e <= 999. In plain language the sub array must be a minimum of two elements long and could be up to 1000 elements long with s=0 and e=999.

The sum value is the total of all elements from numbers[s] to numbers[e] inclusive. As the numbers are signed ints, they can be negative or positive so finding the highest total becomes quite a challenge. The answer I want has both the start and end indices whose elements sum up to give the highest +ve total.

To avoid any possible ambiguity, this means sum up elements numbers[s], numbers[s+1], numbers[s+2].. numbers[e].

Input File

The input will be provided in a text file called numbers.txt in the same location as your exe. It contains 1000 ints, one on each line in the range -10,000 to +10,000 with a random distribution. Note, it will not be the same as the numbers.txt numbers provided here. A different file with the same range of values will be provided.

Output

The output consists of printing three numbers on one line, separated by spaces and then printing the average time (in seconds) to find those three numbers on the next like this:

5 72 23456
0.00076

The first and second numbers on the first line are the start and end index values (s and e ) and the third number is the total of all numbers[s] .. numbers[e] including both numbers[s[] and numbers[e] in the total. The 2nd line is the average time taken to work out the highest sub array total. Please see the "General Tips on Entering" link below for rules and code for timing, especially with regards to average times.

Winning Criteria

The winner is the highest sub-array total computed in under 3 seconds average time. If you get a higher total but take longer than three seconds then it won't be counted. That's timed on my PC which is an i7 850 running Windows 7.

Final Results

There were 16 entries, an excellent turnout. The top six had exceedingly fast times but Tapani's entry blew everything out of the water. Congratulations to him though please note that it had some inline assembler in it which GCC can handle.

  1. Tapani Utriainen(C) Result=OK , Time = 0.000001057 (Sweden)
  2. Arun Prakash M(C++) Result=OK , Time = 0.000002533 (India,31)
  3. Jos Koenis(C++) Result=OK , Time = 0.000002563 (Netherlands,33)
  4. Jon Drane(C) Result=OK , Time = 0.0000071421 (,)
  5. Graeme McDonald (C++) url=website Result=OK , Time = 0.000007282 (Australia,39)
  6. Mariusz Soca(C#) Result=OK , Time = 0.0000092137 (Poland,54)
  7. Fera Louca(C) Result=OK , Time = 0.000400539 (Portugal,)
  8. Keith Corlett(C#) Result=OK , Time = 0.000411051563106258 (,)
  9. David Hohl(C#) Result=OK , Time = 0.000821148 (USA,57)
  10. Gerrit Drost (C#) Result=OK , Time = 0.0039853 (Holland,)
  11. Juhasz Gabor(C++) Result=OK , Time = 0.0134329 (Hungary,)
  12. Fritz Stocker(C#) Result=OK , Time = 0.03708602 (Austria,)
  13. Keith Corlett(C#) Result=OK , Time = 0.0652739824104355 (,)
  14. Mark Mammel(Go) Result=OK , Time = 0.072964173 (,)
  15. Tobias Halingstad(C++) Result=OK , Time = 0.161009 (Norway,)
  16. Amit Kumar(C++) Result=OK , Time = 0.266 (India,)

General Tips on Entering

This is a single page article with tips on things to do and not do when entering challenges. Please read it!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Contest 64 email address with the subject line Programming Contest 64.

It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is December 2, 2012.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 64 - Sum Some Sub-Array

©2014 About.com. All rights reserved.