求长度为k的非连续子序列最大值的最小值：算法正确性验证

给定数组，找出所有长度为k的非连续子序列（子序列中任意两个元素在原数组中不相邻），计算每个子序列的最大值，再求这些最大值中的最小值。例如数组[2,3,5,9]、k=2时，有效子序列为[2,5]、[3,9]、[2,9]，最大值分别为5、9、9，最终结果为5。

我的情况 #

• 已用C语言实现解决该问题的算法，所有测试用例均通过。
• 为确保解决方案可靠，撰写了一份正确性证明，但不确定其质量。
• 核心疑问：
  1. 编写的算法是否正确？
  2. 撰写的正确性证明是否正确？
• 额外需求：
  • 希望得到算法、证明及C语言实现的优化建议
  • 若对原问题存在误解，请指出

算法说明 #

做了两个前提假设：

• 输入序列元素唯一
• 2≤k≤(序列长度+1)/2

算法核心逻辑：将数组升序排序，依次检查每个元素是否能作为长度为k的非连续子序列的最大值，找到第一个满足条件的元素即为结果。

正确性证明 #

定义了相关术语，证明了目标结果是能作为k长度非连续子序列最大值的最小元素，并说明了最长符合条件子序列的构造方式。

C语言实现 #

#include <limits.h> // For INT_MAX
#include <assert.h> // For assert
#include <string.h> // For memcpy
#include <stdlib.h> // For qsort

int compar (const void * first, const void * second) {
    if (* (int *)first < * (int *)second) return -1;
    else if (* (int *)first == * (int *)second) return 0;
    else return 1;
}

void find_k_size_sequence_maxes_min (int array_length, int array[], int k, int * result_min) {
    if (k < 2 || array_length < 2 * k - 1) return;

    int sorted[array_length];
    memcpy(sorted, array, sizeof (int) * array_length);
    qsort(sorted, array_length, sizeof (int), compar);

    for (int t = k - 1; t < array_length; ++t) {
        int index = -1;
        while (array[++index] != sorted[t]);

        int size = 1;

        int last_index = index;
        for (int u = index; u >= 0; --u) {
            if (u < last_index - 1 && array[u] <= sorted[t]) {
                ++size;
                last_index = u;
            }

            if (size >= k) {
                * result_min = sorted[t];
                return;
            }
        }

        last_index = index;
        for (int u = index; u < array_length; ++u) {
            if (u > last_index + 1 && array[u] <= sorted[t]) {
                ++size;
                last_index = u;
            }

            if (size >= k) {
                * result_min = sorted[t];
                return;
            }
        }
    }
}

int main (void) {
    // Test case 1
    int array1[] = { 6, 3, 5, 8, 1, 0, 9, 7, 4, 2, };
    int array1_length = (int)((double)sizeof array1 / sizeof (int));
    int k = 2;
    int min = INT_MAX;
    find_k_size_sequence_maxes_min(array1_length, array1, k, & min);
    assert(min == 2);

    // Test case 2
    int array2[] = { 1, 7, 2, 3, 9, 11, 8, 14, };
    int array2_length = (int)((double)sizeof array2 / sizeof (int));
    k = 2;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array2_length, array2, k, & min);
    assert(min == 2);

    // Test case 3
    k = 3;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array2_length, array2, k, & min);
    assert(min == 8);

    // Test case 4
    k = 4;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array2_length, array2, k, & min);
    assert(min == 9);

    // Test case 5
    int array3[] = { 3, 5, 4, 0, 8, 2, };
    int array3_length = (int)((double)sizeof array3 / sizeof (int));
    k = 3;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array3_length, array3, k, & min);
    assert(min == 3);

    // Test case 6
    int array4[] = { 18, 21, 20, 6 };
    int array4_length = (int)((double)sizeof array4 / sizeof (int));
    k = 2;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array4_length, array4, k, & min);
    assert(min == 18);

    // Test case 7
    int array5_length = 1000000;
    int array5[array5_length];
    for (int m = array5_length - 1; m >= 0; --m) array5[m] = m;
    k = 100;
    min = INT_MAX;
    find_k_size_sequence_maxes_min(array5_length, array5, k, & min);
    assert(min == 198);
}

补充说明 #

• 经优化，排序后的循环可从t=k-1开始以减少迭代次数
• 目前已在原问题下发布解答，仍欢迎进一步优化建议

内容的提问来源于stack exchange，提问作者user20276305