top of page
Caută
  • Poza scriitoruluioanaunciuleanu

Longest Increasing Sub-sequence in C++



Using this algorithm we can find the longest increasing subsequence from a given array. This means that we will find the numbers that are found in a sorted way, from smallest to largest, that are not necessarily adjacent. For example, from 6, 5, 9, the longest increasing subsequence is of value 2, being created by 6 and 9, or by 5 and 9.



// Longest Increasing Subsequence
#include <stdio.h>
#include <stdlib.h>

int longestIncreasingSubsequence(int arrayOfNumbers[], int numberOfElements)
{
    int *lis;
    int maxLength = 0;
    lis = (int*)malloc(sizeof(int) * numberOfElements);

    for (int i = 0; i < numberOfElements; i++)
    {
        lis[i] = 1;
    }

    for (int i = 1; i < numberOfElements; i++)
    {
         for (int j = 0; j < i; j++)
         {
             if (arrayOfNumbers[i] > arrayOfNumbers[j] && lis[i] < lis[j] + 1)
             {
                 lis[i] = lis[j] + 1;
             }
         }
    }

    for (int i = 0; i < numberOfElements; i++)
    {
        if (maxLength < lis[i])
        {
            maxLength = lis[i];
        }
    }
    free(lis);

    return maxLength;
}

int main()
{
    int arrayOfNumbers[] = { 9, 25, 7, 29, 18, 52, 38, 55 };
    int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
    int laxLength = longestIncreasingSubsequence(arrayOfNumbers, numberOfElements);
    printf("The length of the longest increasing subsequence is %d.", laxLength);
    return 0;
}

The   length of the longest increasing subsequence is 5.

53 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit. Solution: 1. static

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed vertically 2 x 1 or horizontally as 1 x 2. Solution: 1. static

bottom of page