1
\$\begingroup\$

Attempting to learn dynamic programming, it seems like the algorithm works. I'm looking to make sure the algorithm is correct (and actually uses dynamic programming correctly) and for pointers on ways to clean up the code.

The algorithm creates a meta data table that has the element's value, the length of its longest sub-sequence, and a pointer to the index of its predecessor with the longest sub-sequence of its own.

Then we use the meta data to collect value with the longest length, then follow its predecessor pointer index to the next value, and add them to our longest sub-sequence in reverse order to reconstruct it until we hit an element with no predecessor.

And now for the code:

class SequenceValueWithMetaData
{
    public int Value { get; private set; }
    public int Length { get; set; }
    public int? predecessorIndexMaybe { get; set; }

    public SequenceValueWithMetaData(int value)
    {
        Value = value;
        Length = 0;
        predecessorIndexMaybe = null;
    }
}

public class Program
{
    static void Main(string[] args)
    {
        List<int> sequence = new List<int> { 2, 4, 3, 5, 1, 7, 6, 9, 8 };

        List<int> longestSubsequence = GetLongestSubSequence(sequence);
        PrintList(sequence);
        PrintList(longestSubsequence);

        PromptForClose();
    }

    private static void PrintList<T>(IEnumerable<T> list)
    {
        foreach (T t in list)
        {
            Console.Write(t + " ");
        }

        Console.WriteLine();
    }

    private static void PromptForClose()
    {
        Console.WriteLine("Press RETURN to close.");
        Console.ReadLine();
    }

    public static List<int> GetLongestSubSequence(List<int> sequence)
    {
        if (sequence == null)
        {
            return null;
        }

        if (sequence.Count <= 0)
        {
            return new List<int>();
        }

        // generate the value table
        List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence);
        if (valueTable == null)
        {
            // Internal Error
            throw new InvalidOperationException("valueTable is null");
        }

        // find largest length in the valueTable and record it to index
        int indexOfLongestLength = 0;
        for (int i = 0; i < valueTable.Count; i++)
        {
            if (valueTable[i].Length > valueTable[indexOfLongestLength].Length)
            {
                indexOfLongestLength = i;
            }
        }

        // create the longest subsequence by finding the longest length,
        //   adding the value to the back of the list, then moving to its predecessor's index
        int currentIndex = indexOfLongestLength;
        int insertionPoint = valueTable[indexOfLongestLength].Length - 1;
        int[] longestSubsequence = new int[valueTable[indexOfLongestLength].Length];
        do
        {
            // add the value at index to the end of longestSubsequence
            longestSubsequence[insertionPoint] = valueTable[currentIndex].Value;
            insertionPoint = insertionPoint - 1;

            // check if there is a predecessor
            int? predecessorIndexMaybe = valueTable[currentIndex].predecessorIndexMaybe;

            // if there is a predecessor, then assign set currentIndex to to the predecessorIndex
            if (predecessorIndexMaybe.HasValue)
            {
                currentIndex = predecessorIndexMaybe.Value;
            }
            else
            {
                // no predecessor, so we're done
                break;
            }
        } while (true); // breaks when there is no predecessor

        return longestSubsequence.ToList();
    }

    private static List<SequenceValueWithMetaData> GenerateValueTableFromSequence(List<int> sequence)
    {
        if (sequence == null)
        {
            // Internal Error
            throw new InvalidOperationException("valueTable is null");
        }

        List<SequenceValueWithMetaData> valueTable = new List<SequenceValueWithMetaData>();

        // for each number in sequence
        foreach (int number in sequence)
        {
            // Create a ValueMetaData for this number and add it to the valueTable
            SequenceValueWithMetaData currentValue = new SequenceValueWithMetaData(number);
            valueTable.Add(currentValue);

            // traverse valueTable looking for the index of the longest length; where the value is < the current number
            int indexOfCurrentLongestLength = 0;
            bool hasPredecessor = false;
            for (int i = 0; i < valueTable.Count; i++)
            {
                // if the value is less than our current value
                if (valueTable[i].Value < currentValue.Value)
                {
                    // at least one value is lower, so there will be a valid predecessor
                    hasPredecessor = true;

                    // if this value has a longer length than the currentLongestLength, then assign its index to the currentLongestLength
                    if (valueTable[i].Length > valueTable[indexOfCurrentLongestLength].Length)
                    {
                        indexOfCurrentLongestLength = i;
                    }
                }
            }

            // record the found's length + 1 into this number's ValueMetaData
            currentValue.Length = valueTable[indexOfCurrentLongestLength].Length + 1;

            // if our currentValue has no predecessor, then set it to null
            if (hasPredecessor == false)
            {
                currentValue.predecessorIndexMaybe = null;
            }
            // else, set currentValue's predecessor to the predecessor with the longest length
            else
            {
                currentValue.predecessorIndexMaybe = indexOfCurrentLongestLength;
            }
        }

        return valueTable;
    }
}

Thanks!

\$\endgroup\$
1
\$\begingroup\$

I don't know whether it's a real dynamic programming or not because the definition is a little bit confusing but I'll try to review it anyway.

First of all your problem can be solved with a single method like this one. It groups elements in ascending order and picks the longest sequence. It works with any T that implements IComparable.

public static IEnumerable<T> LongestSequence<T>(this IEnumerable<T> values) where T : IComparable
{
    return values.Aggregate(new List<List<T>>(), (groups, next) =>
    {
       if (groups.Any())
       {
           var group = groups.FirstOrDefault(x => x.Any() && x.Last().CompareTo(next) < 0);
           if (group != null)
           {
               group.Add(next);
               return groups;
           }
       }

       groups.Add(new List<T> { next });
       return groups;
    })
    .OrderByDescending(x => x.Count)
    .FirstOrDefault();
}

Now let's review your code...


GenerateValueTableFromSequence and the null check

In .net we don't usually return null for collections. We do this so that we can avoid the null-check. We return empty collections which are safe to work with.

So this

List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence);
if (valueTable == null)
{
    // Internal Error
    throw new InvalidOperationException("valueTable is null");
}

would become:

List<SequenceValueWithMetaData> valueTable = GenerateValueTableFromSequence(sequence);
if (!valueTable.Any())
{
    // Internal Error
    return new List<int>(); // or Enumerable.Empty<int>().ToList();
}

There's no need for exeptions. (I'm ignoring the fact that it won't be null anyway looking at the implementation).


private static List<SequenceValueWithMetaData> GenerateValueTableFromSequence(List<int> sequence)
{
    if (sequence == null)
    {
        // Internal Error
        throw new InvalidOperationException("valueTable is null");
    }

If we check arguments we throw the Argument(Null)Exception rather then anything else.

You would throw the InvalidOperationException when

[...] a method call is invalid for the object's current state.

For example if some property of the object is in invalid state etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.