Step by Step solution about How to resolve the algorithm Longest increasing subsequence step by step in the C programming language

The provided C code finds and prints the longest increasing subsequence (LIS) in an array of integers. The LIS is the longest sequence of elements such that each element is greater than the previous element.

The code uses a dynamic programming approach to solve the problem.

• The function lis takes two arguments: an array of integers and the length of the array.

• The function first creates an array of struct nodes, where each node has three fields: val (the value of the node), len (the length of the longest increasing subsequence that ends at this node), and next (a pointer to the next node in the longest increasing subsequence).

• The function then initializes the val fields of the nodes to the values in the input array.

• The function then iterates over the nodes in the array in reverse order.

• For each node, the function finds the longest increasing subsequence that can follow this node. This is done by iterating over the remaining nodes in the array and checking if they are greater than the current node and have a longer length. If such a node is found, the next and len fields of the current node are updated accordingly.

• After iterating over all the nodes, the function finds the node with the longest length. This is the longest increasing subsequence in the input array.

• The function then prints the longest increasing subsequence by following the next pointers in the nodes.

The code also includes a main function that demonstrates the use of the lis function. The main function creates two arrays of integers and calls the lis function on each array to find and print the longest increasing subsequence.

#include <stdio.h>
#include <stdlib.h>

struct node {
	int val, len;
	struct node *next;
};

void lis(int *v, int len)
{
	int i;
	struct node *p, *n = calloc(len, sizeof *n);
	for (i = 0; i < len; i++)
		n[i].val = v[i];

	for (i = len; i--; ) {
		// find longest chain that can follow n[i]
		for (p = n + i; p++ < n + len; ) {
			if (p->val > n[i].val && p->len >= n[i].len) {
				n[i].next = p;
				n[i].len = p->len + 1;
			}
		}
	}

	// find longest chain
	for (i = 0, p = n; i < len; i++)
		if (n[i].len > p->len) p = n + i;

	do printf(" %d", p->val); while ((p = p->next));
	putchar('\n');

	free(n);
}

int main(void)
{
	int x[] = { 3, 2, 6, 4, 5, 1 };
	int y[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };

	lis(x, sizeof(x) / sizeof(int));
	lis(y, sizeof(y) / sizeof(int));
	return 0;
}