Find the LIS with the maximum sum

Question

I have this code for finding the Longest Increasing Subsequence (LIS) but when i test my code I dont get maximum sum, for example:

if I type 20 1 4 3 10 the answer is 1 3 10, but i need 1 4 10 This is my code in C:

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

#define INT_INF 1000

int search_replace(int *lis, int left, int right, int key) {
    int mid;

    for (mid = (left+right)/2; left <= right; mid = (left+right)/2) {
            if (lis[mid] > key) {
                    right = mid - 1;
            } else if (lis[mid] == key) {
                    return mid;
            } else if (mid+1 <= right && lis[mid+1] >= key) {
                    lis[mid+1] = key;
                    return mid+1;
            } else {
                    left = mid + 1;
            }
    }
    if (mid == left) {
            lis[mid] = key;
            return mid;
    }
    lis[mid+1] = key;
    return mid+1;
}

int main() {
    int size, i;

    scanf(" %d", &size);

    int A[size];

    for(i = 0; i < size; i++){
        scanf(" %d", &A[i]);
    }

    int tmp, lis_length = -1;
    int *answer;
    int LIS[size];
    int index[size];

    LIS[0] = A[0];
    for (i = 1; i < size; ++i) {
            LIS[i] = INT_INF;
    }

    for (i = 1; i < size; ++i) {
            index[i] = search_replace(LIS, 0, i, A[i]);
            if (lis_length < index[i]) {
                    lis_length = index[i];
            }
    }

    answer = (int*) malloc((lis_length+1) * sizeof(int));
    for (i = size-1, tmp = lis_length; i >= 0; --i) {
            if (index[i] == tmp) {
                    answer[tmp] = A[i];
                    --tmp;
            }
    }

    printf("LIS: ");
    for (i = 0; i < lis_length+1; ++i) {
            printf("%d ", answer[i]);
    }
    printf("\n");

    return 0;
}

first input is for number of elements in array.

I aleready tried with this post: Find the Longest Increasing Subsequence with the Maximum Sum , and few others but no success.

score 0 · Answer 1 · edited Jun 20 '20 at 09:12

I have analyzed your code and found your problem: you don't have code for finding the lis with maximum sum, you have the simple lis searching only. I have added the missing part and now, the code is working as it should. Also, I wrote my own solution, with another lis searching algorithm and without the binary search.

Note: the (left+right)/2 method for finding the middle value, have a problem - Nearly All Binary Searches and Mergesorts are Broken .

Your code with my addition:

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

#define INT_INF 1000

int search_replace(int *lis, int left, int right, int key) {
    int mid;
    for (mid = (left+right)/2; left <= right; mid = (left+right)/2) {
        if (lis[mid] > key) {
            right = mid - 1;
        } else if (lis[mid] == key) {
            return mid;
        } else if (mid+1 <= right && lis[mid+1] >= key) {
            lis[mid+1] = key;
            return mid+1;
        } else {
            left = mid + 1;
        }
    }
    if (mid == left) {
        lis[mid] = key;
        return mid;
    }
    lis[mid+1] = key;
    return mid+1;
}

int main() {
    int size, i;

    scanf(" %d", &size);

    int A[size];

    for(i = 0; i < size; i++){
        scanf(" %d", &A[i]);
    }

    int tmp, lis_length = -1;
    int LIS[size];
    int index[size];

    LIS[0] = A[0];
    for (i = 1; i < size; ++i) {
        LIS[i] = INT_INF;
    }

    for (i = 1; i < size; ++i) {
        index[i] = search_replace(LIS, 0, i, A[i]);
        if (lis_length < index[i]) {
            lis_length = index[i];
        }
    }
    
    //////// my addition starts
    int max, j;
    // INT_MAX - the maximum number of the integer type.
    // The "limits.h" header is needed for this.
    int prev = INT_MAX;
    int answer[lis_length + 1];
    // Iterating through the "index" values.
    // On the each iteration, the checking all sequences 
    // with the same length
    // and determining the max value among them.
    // Starts from the lis_length and goes to the zero.
    for(i = lis_length; i >= 0; i--) {
        max = INT_MIN;
        for(j = 0; j < size; j++) {
            if(    index[j] == i 
                && A[j] > max 
                && A[j] < prev) {
                    
                max = A[j];
            }
        }
        answer[i] = max;
        prev = max;
    }
    //////// my addition ends

    printf("LIS: ");
    for (i = 0; i < lis_length+1; ++i) {
        printf("%d ", answer[i]);
    }
    printf("\n");

    return 0;
}

This is my solution with comments.

I used this algorithm for the lis determination. Ask questions, if you need.

#include <stdio.h>
#include <limits.h>

int main() {
    int size = 0;
    int arr_nums[100];
    // Initialize all array values to the one. This is the GCC feature.
    int seq_lens[100] = {[0 ... 99] = 1};

    // Gets input numbers.
    while(scanf("%d", arr_nums + size) == 1) {
        size++;
    }
    // Fill the seq_lens array with sequences's lenghts.
    int i, j;
    int lis_num = 1;
    for(i = 1; i < size; i++) {
        for(j = 0; j <= i; j++) {
            if(     arr_nums[i] > arr_nums[j] 
                && (seq_lens[j] + 1 > seq_lens[i])) {

                    seq_lens[i] = seq_lens[j] + 1;
            }
        }
        // Finding the LIS number (the maximum sequence length).
        // If the previous LIS number is lesser then current, 
        // change it to the current.
        if(lis_num < seq_lens[i])
            lis_num = seq_lens[i];
    }

    // Finding the LIS with the maximum sum
    int max;
    // INT_MAX - the maximum number of the integer type.
    // The "limits.h" header is needed for this.
    int prev = INT_MAX;
    int lis_arr[lis_num];
    // Iterating through the seq_lens values.
    // On the each iteration, the checking all sequences with the same length
    // and determining the max value among them.
    // Starts from the LIS (the longest sequence number) 
    // and goes to the one (the minimum possible sequence number).
    for(i = lis_num; i > 0; i--) {
        max = INT_MIN;
        for(j = 0; j < size; j++) {
            if(    seq_lens[j] == i 
                && arr_nums[j] > max 
                && arr_nums[j] < prev) {
                    
                max = arr_nums[j];
            }
        }
        lis_arr[i - 1] = max;
        prev = max;
    }

    printf("The longest increasing sequence number is:\n%d\n", lis_num);

    puts("\nThe longest increasing sequence with the max sum is: ");
    for(i = 0; i < lis_num; i++) {
        printf("%d ", lis_arr[i]);
    }
    puts("");

    return 0;
}

Input

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Output

The longest increasing sequence number is:
6

The longest increasing sequence with the max sum is: 
0 4 6 9 13 15

Find the LIS with the maximum sum

1 Answers1

Your code with my addition:

This is my solution with comments.