This article covers several dynamic programming problems, including finding the maximum subarray sum, the longest increasing subsequence, the longest common subsequence, the longest palindromic substring, and finding the longest path in a Directed Acyclic Graph (DAG).

Maximum Subarray Sum

This problem requires finding a contiguous subarray within a one-dimensional array of numbers that has the largest sum. The solution uses dynamic programming to track the sum of the maximum subarray ending at each position.

#include <cstdio>
#include <cstring>

#define MAX_SIZE 10005

struct SubarrayInfo {
    int start_val, end_val; // Values of the start and end elements
    int current_sum;
} dp[MAX_SIZE]; // dp[i] stores info for max subarray ending at index i

int main() {
    int array_size;
    int input_array[MAX_SIZE];

    while (scanf("%d", &array_size) && array_size) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < array_size; ++i) {
            scanf("%d", &input_array[i]);
        }

        dp[0].start_val = dp[0].end_val = dp[0].current_sum = input_array[0];

        for (int i = 1; i < array_size; ++i) {
            int current_element = input_array[i];
            if (current_element >= dp[i - 1].current_sum + current_element) {
                // Start a new subarray at the current element
                dp[i].start_val = dp[i].end_val = dp[i].current_sum = current_element;
            } else {
                // Extend the previous subarray
                dp[i].start_val = dp[i - 1].start_val;
                dp[i].end_val = current_element;
                dp[i].current_sum = dp[i - 1].current_sum + current_element;
            }
        }

        int best_index = 0;
        for (int i = 1; i < array_size; ++i) {
            if (dp[i].current_sum > dp[best_index].current_sum) {
                best_index = i;
            }
        }

        if (dp[best_index].current_sum < 0) {
            // If the max sum is negative, output 0 and the first and last elements of the original array
            printf("0 %d %d\n", input_array[0], input_array[array_size - 1]);
        } else {
            printf("%d %d %d\n", dp[best_index].current_sum, dp[best_index].start_val, dp[best_index].end_val);
        }
    }
    return 0;
}

Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence problem finds the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. The solution uses dynamic programming where dp[i] stores the length of the LIS ending at index i.

#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_SIZE 1005

int main() {
    int sequence_length;
    int sequence[MAX_SIZE], dp_lis[MAX_SIZE]; // dp_lis[i] stores the length of LIS ending at sequence[i]
    scanf("%d", &sequence_length);
    for (int i = 0; i < sequence_length; ++i) {
        scanf("%d", &sequence[i]);
    }

    int max_lis_length = -1;
    for (int i = 0; i < sequence_length; ++i) {
        dp_lis[i] = 1; // Initialize LIS length for the current element to 1
        for (int j = 0; j < i; ++j) {
            if (sequence[j] <= sequence[i]) { // For non-decreasing subsequence
                dp_lis[i] = max(dp_lis[i], 1 + dp_lis[j]);
            }
        }
        if (dp_lis[i] > max_lis_length) {
            max_lis_length = dp_lis[i];
        }
    }

    printf("%d\n", max_lis_length);
    return 0;
}

Longest Common Subsequence (LCS)

The Longest Common Subsequence problem finds the longest subsequence common to two sequences. This implementation uses a 2D DP table where dp[i+1][j+1] stores the length of the LCS of the first i+1 characters of string a and the first j+1 characters of string b.

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

#define MAX_LEN 105
using namespace std;

int main() {
    string str_a, str_b;
    int dp_lcs[MAX_LEN][MAX_LEN]; // dp_lcs[i+1][j+1] stores LCS length for str_a[0..i] and str_b[0..j]

    while (cin >> str_a >> str_b) {
        // Initialize DP table with 0s
        for (int i = 0; i <= str_a.length(); ++i) {
            dp_lcs[i][0] = 0;
        }
        for (int i = 0; i <= str_b.length(); ++i) {
            dp_lcs[0][i] = 0;
        }

        // Fill DP table
        for (int i = 0; i < str_a.length(); ++i) {
            for (int j = 0; j < str_b.length(); ++j) {
                if (str_a[i] == str_b[j]) {
                    dp_lcs[i + 1][j + 1] = dp_lcs[i][j] + 1;
                } else {
                    dp_lcs[i + 1][j + 1] = max(dp_lcs[i][j + 1], dp_lcs[i + 1][j]);
                }
            }
        }
        printf("%d\n", dp_lcs[str_a.length()][str_b.length()]);
    }
    return 0;
}

Longest Palindromic Substring

This problem involves finding the longest substring within a given string that is a palindrome. The approach uses a DP table dp[i][j] to indicate whether the substring from index i to j is a palindrome. It also maps characters from the input buffer to a processed string s for easier comparison and stores the original buffer indices.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype> // For isalpha, isdigit, tolower

#define MAX_BUFFER_SIZE 5005
char buffer[MAX_BUFFER_SIZE], processed_string[MAX_BUFFER_SIZE];
int buffer_index_map[MAX_BUFFER_SIZE]; // Maps index in processed_string to index in buffer
bool palindrome_dp[MAX_BUFFER_SIZE][MAX_BUFFER_SIZE] = {false}; // palindrome_dp[i][j] is true if processed_string[i..j] is a palindrome

int main() {
    gets(buffer);
    int processed_len = 0;

    // Populate processed_string with alphanumeric characters (lowercase) and map indices
    for (int i = 0; i < strlen(buffer); ++i) {
        if (isalpha(buffer[i])) {
            processed_string[processed_len] = tolower(buffer[i]);
            buffer_index_map[processed_len] = i;
            processed_len++;
        } else if (isdigit(buffer[i])) {
            processed_string[processed_len] = buffer[i];
            buffer_index_map[processed_len] = i;
            processed_len++;
        }
    }

    int max_palindrome_len = 1, start_index = 0;

    // Base cases: single characters and adjacent identical characters
    for (int i = 0; i < processed_len; ++i) {
        palindrome_dp[i][i] = true;
        if (i < processed_len - 1 && processed_string[i] == processed_string[i + 1]) {
            palindrome_dp[i][i + 1] = true;
            if (max_palindrome_len < 2) {
                max_palindrome_len = 2;
                start_index = i;
            }
        }
    }

    // Fill DP table for lengths 3 and greater
    for (int len = 3; len <= processed_len; ++len) {
        for (int i = 0; i + len - 1 < processed_len; ++i) {
            int j = i + len - 1;
            if (processed_string[i] == processed_string[j] && palindrome_dp[i + 1][j - 1]) {
                palindrome_dp[i][j] = true;
                if (max_palindrome_len < len) {
                    max_palindrome_len = len;
                    start_index = i;
                }
            }
        }
    }

    // Print the longest palindromic substring from the original buffer
    for (int i = buffer_index_map[start_index]; i <= buffer_index_map[start_index + max_palindrome_len - 1]; ++i) {
        printf("%c", buffer[i]);
    }
    printf("\n");

    return 0;
}

Critical Path in Project Management

This problem is related to finding the critical path in a project, which is the sequence of tasks that determines the duration of the project. It's solved using dynamic programming. The dp[i] array stores the length of the longest path starting from node i. The graph is represented by an adjacency matrix G, and INF denotes no edge. choose[i] stores the next node in the longest path starting from i.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
#define MAX_NODES 20
#define INF 0x3fffffff

int num_nodes, graph[MAX_NODES][MAX_NODES]; // Adjacency matrix for the graph
int dp_path_length[MAX_NODES]; // dp_path_length[i] = longest path length starting from node i
int next_node_in_path[MAX_NODES]; // Stores the next node in the longest path from node i

// Recursive function with memoization to calculate the longest path starting from node i
int calculate_longest_path(int current_node) {
    if (dp_path_length[current_node] > 0) {
        return dp_path_length[current_node];
    }

    for (int neighbor_node = 0; neighbor_node < num_nodes; ++neighbor_node) {
        if (graph[current_node][neighbor_node] != INF) {
            int path_via_neighbor = calculate_longest_path(neighbor_node) + graph[current_node][neighbor_node];
            if (path_via_neighbor > dp_path_length[current_node]) {
                dp_path_length[current_node] = path_via_neighbor;
                next_node_in_path[current_node] = neighbor_node;
            }
        }
    }
    return dp_path_length[current_node];
}

// Function to print the critical path
void print_critical_path(int start_node) {
    while (next_node_in_path[start_node] != -1) {
        printf("(%c,%c) ", start_node + 97, next_node_in_path[start_node] + 97);
        start_node = next_node_in_path[start_node];
    }
}

int main() {
    int num_test_cases, num_edges, edge_weight;
    scanf("%d", &num_test_cases);
    while (num_test_cases--) {
        // Initialize graph and DP arrays
        for (int i = 0; i < MAX_NODES; ++i) {
            for (int j = 0; j < MAX_NODES; ++j) {
                graph[i][j] = INF;
            }
        }
        fill(dp_path_length, dp_path_length + MAX_NODES, 0);
        fill(next_node_in_path, next_node_in_path + MAX_NODES, -1);

        scanf("%d%d", &num_nodes, &num_edges);
        char node_label;
        // Consume node labels (not used in this logic but read for input consistnecy)
        for (int i = 0; i < num_nodes; ++i) {
            cin >> node_label;
        }

        // Read edges and weights
        char node_a, node_b;
        for (int i = 0; i < num_edges; ++i) {
            cin >> node_a >> node_b >> edge_weight;
            graph[node_a - 97][node_b - 97] = edge_weight;
        }

        int max_total_path = 0, critical_start_node = -1;
        for (int i = 0; i < num_nodes; ++i) {
            int current_path_len = calculate_longest_path(i);
            if (current_path_len > max_total_path) {
                max_total_path = current_path_len;
                critical_start_node = i;
            }
        }

        if (critical_start_node != -1) {
             print_critical_path(critical_start_node);
        }
        printf("%d\n", max_total_path);
    }
    return 0;
}

Longest Path in a DAG (Rectangular Nesting)

This problem involves finding the maximum number of rectangles that can be nested within each other. It's modeled as finding the longest path in a Directed Acyclic Graph (DAG). Each rectangle is a node, and an edge exists from rectangle A to rectangle B if A can be nested inside B. The edge weight is 1. The DP state dp[i] represents the longest path starting from node i.

#include <cstdio>
#include <algorithm>

#define MAX_RECTANGLES 1005
#define INF 0x3fffffff

using namespace std;

struct Rectangle {
    int length, width;
} rectangles[MAX_RECTANGLES];

int num_rectangles, adjacency_matrix[MAX_RECTANGLES][MAX_RECTANGLES];
int dp_longest_path[MAX_RECTANGLES];

// DP function to find the longest path starting from node i
int find_longest_path(int current_node) {
    if (dp_longest_path[current_node] > 0) {
        return dp_longest_path[current_node];
    }

    for (int next_node = 0; next_node < num_rectangles; ++next_node) {
        if (adjacency_matrix[current_node][next_node] != INF) {
            dp_longest_path[current_node] = max(dp_longest_path[current_node], find_longest_path(next_node) + adjacency_matrix[current_node][next_node]);
        }
    }
    return dp_longest_path[current_node];
}

int main() {
    int num_test_cases, dim1, dim2;
    scanf("%d", &num_test_cases);
    while (num_test_cases--) {
        // Initialize adjacency matrix and DP array
        for (int i = 0; i < MAX_RECTANGLES; ++i) {
            for (int j = 0; j < MAX_RECTANGLES; ++j) {
                adjacency_matrix[i][j] = INF;
            }
        }
        fill(dp_longest_path, dp_longest_path + MAX_RECTANGLES, 0);

        scanf("%d", &num_rectangles);
        for (int i = 0; i < num_rectangles; ++i) {
            scanf("%d%d", &dim1, &dim2);
            // Standardize dimensions: length >= width
            if (dim1 >= dim2) {
                rectangles[i].length = dim1;
                rectangles[i].width = dim2;
            } else {
                rectangles[i].length = dim2;
                rectangles[i].width = dim1;
            }
        }

        // Build the DAG based on nesting possibility
        for (int i = 0; i < num_rectangles - 1; ++i) {
            for (int j = i + 1; j < num_rectangles; ++j) {
                // Check if rectangle i can be nested inside rectangle j
                if (rectangles[i].length < rectangles[j].length && rectangles[i].width < rectangles[j].width) {
                    adjacency_matrix[i][j] = 1;
                }
                 // Check if rectangle j can be nested inside rectangle i
                if (rectangles[j].length < rectangles[i].length && rectangles[j].width < rectangles[i].width) {
                    adjacency_matrix[j][i] = 1;
                }
            }
        }

        int max_nesting_depth = 0, current_path_len;
        for (int i = 0; i < num_rectangles; ++i) {
            current_path_len = find_longest_path(i);
            if (current_path_len > max_nesting_depth) {
                max_nesting_depth = current_path_len;
            }
        }

        // The result is the maximum depth + 1 (to include the outermost rectangle)
        printf("%d\n", max_nesting_depth + 1);
    }
    return 0;
}