Help with pseudo code / C#

roger

I need help coding the following pseudo code into C#.

The 3 algorithms are search methods for a program which can look through a set of data to find the subsequence of values which add
up to the highest total value.

So for example with the data set.

10 -6 12 -17 9 8 -2

the algorithm(s) show that the "best" value was 17 from array index 4 to array index 5 if you go through it. (9 + 8)

10 - 6 = 4
10 - 6 + 12 = 16
10 - 6 + 12 - 17 = -1
10 - 6 + 12 - 17 + 9 = 8
10 - 6 + 12 - 17 + 9 + 8 = 16
10 - 6 + 12 - 17 + 9 + 8 - 2 = 14
-6 + 12 = 6
-6 +12 -17 = -11
-6 +12 -17 + 9 = -2
etc

For every possible start position // every array index
For every possible end position // rest of array from current start
{
Set subtotal to 0
For every value in subseq // between current start and end
Add profit value to subtotal
Update subseq info when subtotal exceeds current best total
}

For every possible start position...
Set subtotal to 0
For every possible end position...
{
Add end position’s profit value to subtotal
Update subseq if subtotal exceeds current best total
}

Set start position to 0, subtotal to 0
For every profit value... // index from 0 to end of array as end position
{
Add value to subtotal
Keep subseq info (start, end, total) if total exceeds current best
If total is less than 0,
set start position to next index and set total to 0
}

I need help creating C# versions of these methods which compile and run.

Thanks

3 Replies

Know the answer? Post it — somebody with the same question will find it here.

Alan18y ago
I don't find the explanations of the algorithms particularly clear but I've had a go at the first two below.

I'll leave the third one to you if you can understand it - it made no sense at all to me!

using System;

class Program
{
    static void Main()
    {
       int bestStart, bestEnd, loops;
       double bestTotal;
       double[] data = new double[]{10, -6, 12, -17, 9, 8, -2};
       Search1(data, out bestStart, out bestEnd, out bestTotal, out loops);

       Console.WriteLine("Results for method 1\n");
       Console.WriteLine(" Best total is {0} from index {1} to {2}", bestTotal, bestStart, bestEnd);
       Console.WriteLine(" Number of loops {0}\n", loops);

       Search2(data, out bestStart, out bestEnd, out bestTotal, out loops);
       Console.WriteLine("Results for method 2\n");
       Console.WriteLine(" Best total is {0} from index {1} to {2}", bestTotal, bestStart, bestEnd);
       Console.WriteLine(" Number of loops {0}\n", loops);

       Console.ReadLine();
    }

    public static void Search1(double[] data, out int bestStart,
        out int bestEnd, out double bestTotal, out int loops)
    {
       bestTotal = 0;
       bestStart = 0;
       bestEnd = 0;
       loops = 0;
       double subTotal = 0.0;

       for(int i = 0 ; i < data.Length - 1 ; i++)
       {
          loops++;
          for (int j = i + 1; j < data.Length ; j++)
          {
             loops++;
             subTotal = 0.0;
             for (int k = i; k <= j; k++)
             {
                loops++;
                subTotal += data[k];
                if (subTotal > bestTotal)
                {
                   bestTotal = subTotal;
                   bestStart = i;
                   bestEnd = j;
                }
             }
          }
       }
    }

    public static void Search2(double[] data, out int bestStart,
        out int bestEnd, out double bestTotal, out int loops)
    {
       bestTotal = 0;
       bestStart = 0;
       bestEnd = 0;
       loops = 0;
       double subTotal = 0.0;

       for(int i = 0 ; i < data.Length -1 ; i++)
       {
          loops++;
          subTotal = data[i];
          for (int j = i + 1; j < data.Length ; j++)
          {
             loops++;
             subTotal += data[j];
             if (subTotal > bestTotal)
             {
                bestTotal = subTotal;
                bestStart = i;
                bestEnd = j;
             }
          }
       }
    }

}
roger18y ago
I have tried. I understand the algorithms in my head but cannot put it into C# :(

This is completely wrong and bad I know but I cant do any better:

Algorithm 1

public static void Search1(double[] data, out int bestStart,
        out int bestEnd, out double bestTotal, out int loops)
        {
            bestTotal = 0;
            bestStart = 0;
            bestEnd = 0;
            loops = 0;
            subTotal = 0;

            for( int i = 0 ; i < data.Length ; i++)
            {
                data [i] =


                /*subtotal = 0;
                i >= currentStart;
                i <= currentEnd;
                bestTotal = bestTotal + subTotal;
                subTotal > bestTotal;*/
            }
                for (int j = 0; j > data.Length; j--)
                {
                    subtotal = 0;
                    i >= bestStart;
                    i <= bestEnd;
                    bestTotal = bestTotal + subTotal;
                    subTotal > bestTotal;
                }
            for (int k = i; k ,< j; k++)
         }

Algorthm 3

public static void Search3(double[] data, out int bestStart,
out int bestEnd, out double bestTotal, out int loops)
{
bestTotal = 0;
bestStart = 0;
bestEnd = 0;
loops = 0;
subTotal = 0;

for (int i = 0; i < data.Length; i++)
{
subtotal = subtotal + i;
if (subTotal > bestTotal);
{
bestTotal = bestTotal;
}
if (subTotal > bestStart);
{
bestTotal = bestStart;
}
if (subTotal > bestEnd);
{
bestTotal = bestEnd;
}

if (total < 0) ;
i = [next index?]
total = 0

Any help with the C# is appreciated.
Bechir Bejaoui18y ago
you should make some efforts!!!!! it is not hard to do