Rank: Administration
Groups: Administration
Joined: 7/24/2005
Posts: 14
Location: Richardson, TX
|
This one is a little trickier. Most people will try to brute force it... that is to say they will simply add every possible combination of integers and see which on is the largest. This works fine for small arrays, but what about an array with a million integers? I think it might run for a little while. You are looking for candidates that come up with an elegant solution. It is possible to iterate the array just once and come up with the correct answer.
Code:/// <summary> /// This method should return the greatest possible sum of consecutive integers within the array "numbers" /// /// Please note that the solution should be as efficient as possible ans not be breakable. /// /// If all numbers in the array are negative, return 0 /// </summary> /// <param name="numbers">Integer array</param> /// <returns></returns> public static int GreatestConsecutiveSum(int[] numbers) { // Examples //-1, -2, -3 returns 0 // 0, 1, 2, 3, -1 returns 6 // -10, 1, 2, 3 returns 6 // 1, 2, 3, -10, 20 returns 20 // 1, 2, 3, -5, 20 returns 21 return 0; }
Please post any solutions. I will post mine in a few weeks.
If I have seen further than others, it is by standing upon the shoulders of giants.
~Sir Isaac Newton
If I have not seen as far as others, it is because giants were standing on my shoulders.
~Hal Abelson
|
Rank: Administration
Groups: Administration
Joined: 7/24/2005
Posts: 14
Location: Richardson, TX
|
This is my favorite to see someone do really well. The trick is to set two variables, one as a working variable and one that contains the highest sum found so far. You can iterate the array once, and reset the working variable any time it dips below zero, since the lowest number we will allow as a return value is zero. Then you just reset the highest value when the working one goes above it.
Code:/// <summary> /// This method should return the greatest possible sum of consecutive integers within the array "numbers" /// /// Please note that the solution should be as efficient as possible ans not be breakable. /// /// If all numbers in the array are negative, return 0 /// </summary> /// <param name="numbers">Integer array</param> /// <returns></returns> public static int GreatestConsecutiveSum(int[] numbers) { // Examples //-1, -2, -3 returns 0 // 0, 1, 2, 3, -1 returns 6 // -10, 1, 2, 3 returns 6 // 1, 2, 3, -10, 20 returns 20 // 1, 2, 3, -5, 20 returns 21 int sum = 0; // Variable to hold greatest sum int temp = 0; // Working variable for (int i = 0; i < numbers.Length; i++) { temp += numbers[i]; if (temp < 0) { temp = 0; } if (temp > sum) { sum = temp; } } // Return answer return sum; }
If I have seen further than others, it is by standing upon the shoulders of giants.
~Sir Isaac Newton
If I have not seen as far as others, it is because giants were standing on my shoulders.
~Hal Abelson
|
