How is this solution an example of dynamic programming?

A lecturer gave this question in class: [question]

A sequence of n integers is stored in an array A[1..n]. An integer a in A is called the majority if it appears more than n/2 times in A.

An O(n) algorithm can be devised to find the majority based on the following observation: if two different elements in the original sequence are removed, then the majority in the original sequence remains the majority in the new sequence. Using this observation, or otherwise, write programming code to find the majority, if one exists, in O(n) time.

for which this solution was accepted [solution]

int findCandidate(int[] a)
{
    int maj_index = 0;
    int count = 1;
    for (int i=1;i<a.length;i++)
    {
  开发者_如何学编程      if (a[maj_index] == a[i])
            count++;
        else
            count--;

        if (count == 0)
        {
            maj_index =i;
            count++;
        }
    }
    return a[maj_index];
}

int findMajority(int[] a)
{
    int c = findCandidate(a);
    int count = 0;
    for (int i=0;i<a.length;i++)
        if (a[i] == c) count++;

    if (count > n/2) return c;
    return -1;//just a marker - no majority found
}

I can't see how the solution provided is a dynamic solution. And I can't see how based on the wording, he pulled that code out.

The origin of the term dynamic programming is trying to describe a really awesome way of optimizing certain kinds of solutions (dynamic was used since it sounded punchier). In other words, when you see "dynamic programming", you need to translate it into "awesome optimization".

'Dynamic programming' has nothing to do with dynamic allocation of memory or whatever, it's just an old term. In fact, it has little to do with modern meaing of "programming" also.

It is a method of solving of specific class of problems - when an optimal solution of subproblem is guaranteed to be part of optimal solution of bigger problem. For instance, if you want to pay $567 with a smallest amount of bills, the solution will contain at least one of solutions for $1..$566 and one more bill.

The code is just an application of the algorithm.

This is dynamic programming because the findCandidate function is breaking down the provided array into smaller, more manageable parts. In this case, he starts with the first array as a candidate for the majority. By increasing the count when it is encountered and decreasing the count when it is not, he determines if this is true. When the count equals zero, we know that the first i characters do not have a majority. By continually calculating the local majority we don't need to iterate through the array more than once in the candidate identification phase. We then check to see if that candidate is actually the majority by going through the array a second time, giving us O(n). It actually runs in 2n time, since we iterate twice, but the constant doesn't matter.