algorithm - 2 个唯一元素的最大总和

Question

假设你有一个数组，你有 2 个盒子，你可以在其中放置独特的元素

{a,b,b,c,b,b,c,d}

可以从数组的任意位置开始，但只能向右移动。在每个篮子中，您只能放置一种元素。例如，如果 a 在篮子里，只有 a 可以超过它。当您不能将元素放入任何一个框中时，您就会停止。

从这样的数组中，您最多可以将多少个元素放入两个框中。

从这个数组中，答案是 6，因为如果你从索引 1 开始，你可以在一个篮子里放 4b，在另一个篮子里放两个 c，所以总共 6。

谁能为这样的问题解释一个有效的算法，因为数组可以变得非常大并且内部可以有许多不同类型的元素

Answer 1

您可以在仅对输入进行一次迭代的同时进行计算，并且无需存储段。您只需要跟踪当前段中的两个字符、段的长度以及段末相同字符的数量。所以时间复杂度是 O(n)，空间复杂度是 O(1)。

function largestPair(input) {
    var len = 0;     // length of segment
    var run = 0;     // number of identical characters at end
    var max = 0;     // length of longest segment
    var cur = '';    // last character in segment
    var prv = '';    // other character in segment

    for (var i = 0; i < input.length; i++) {
        if (input[i] == cur) {      // same as last
            ++len;
            ++run;
        }
        else if (input[i] == prv) { // same as other
            prv = cur;
            cur = input[i];
            ++len;
            run = 1;
        }
        else {                      // new character
            prv = cur;
            cur = input[i];
            len = run + 1;
            run = 1;
        }
        if (len > max) max = len;
    }
    return max;
}
document.write(largestPair(['a','b','b','c','b','b','c','d']) + "<br>");
document.write(largestPair(['a','b','a','c','d','c','e','a','b']) + "<br>");
document.write(largestPair(['c','a','a','c','a','c','b','b','b']) + "<br>");
document.write(largestPair(['a','b','c','d','e','f','g','h','i']) + "<br>");
document.write(largestPair(['a','a']) + "<br>");
document.write(largestPair(['a']) + "<br>");

或者，更简洁但不太明显:

function largestPair(input) {
    var len = 0;     // length of segment
    var run = 0;     // number of identical characters at end
    var max = 0;     // length of longest segment
    var cur = '';    // last character in segment
    var prv = '';    // other character in segment

    for (var i = 0; i < input.length; i++) {
        if (input[i] == cur) {
            ++len;
            ++run;
        } else {
            len = (input[i] == prv ? len : run) + 1;
            run = 1;
            prv = cur;
            cur = input[i];
        }
        if (len > max) max = len;
    }
    return max;
}