DP + 滚动数组优化

该题类似 $LC$ 经典题 LCR 089. 打家劫舍

定义 $f[i]$：表示前 $i$ 个字符的松散子序列的最大价值，初始 $f[1] = s[1] -$’$a$’$+ 1$。

选择当前字符：由于选择的字符间下标间隔至少为 $2$，当前状态仅和上上一层状态相关，则$f[i] = f[i - 2] + s[i] -$’$a$’$+ 1$

不选当前字符：则当前状态和上一层状态相等：$f[i] = f[i - 1]$

在两者之间取最大值，状态转移方程：

• $f[i] = max(f[i - 1], f[i - 2] + s[i] -$’$a$’$+ 1)$

由于当前状态只和上层状态和上上层状态相关，可以用滚动数组优化，达到 $O(1)$ 空间复杂度

附C++，Java，Python3，JavaScript，Go代码

C++代码：（运行时间：108 ms，运行空间：1248 KB）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

string s;
int n, res;

int main()
{
    cin >> s;
    s = " " + s;
    int n = s.size();
    int f0 = 0, f1 = s[1] - 'a' + 1;
    for (int i = 2; i <= n; i ++ ) {
        int f2 = max(f1, f0 + s[i] - 'a' + 1);
        f0 = f1;
        f1 = f2;
    }
    cout << f1 << endl;
    return 0;
}

Java代码：（运行时间：2340 ms，运行空间：46252 KB）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = " " + sc.next();
        int n = s.length() - 1;
        int f0 = 0, f1 = (char)s.charAt(1) - 'a' + 1;
        for (int i = 2; i <= n; i ++ ) {
            int f2 = Math.max(f1, f0 + (char)s.charAt(i) - 'a' + 1);
            f0 = f1;
            f1 = f2;
        }
        System.out.println(f1);
    }
}

Python3代码：（运行时间：1006 ms，运行空间：48708 KB）

s = input()
n, res = len(s), 0
f0, f1 = 0, ord(s[0]) - 96
for i in range(2, n + 1):
    f2 = max(f1, f0 + ord(s[i - 1]) - 96)
    f0, f1 = f1, f2
print(f1)

JavaScript代码：（运行时间：826 ms，运行空间：13740 KB）

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let s, n, res;
rl.on('line', (input) => {
    if (!s) {
        s = input.trim();
        n = s.length;
        f0 = 0;
        f1 = s.charCodeAt(0) - 96;
        for (let i = 2; i <= n; i ++ ) {
            f2 = Math.max(f1, f0 + s.charCodeAt(i - 1) - 96)
            f0 = f1;
            f1 = f2;
        }
        console.log(f1);
    }
});

rl.on('close', () => {});

Go代码：（运行时间：6911 ms，运行空间：10456 KB）

package main

import (
    . "fmt"    
)

func main() {
    var s string
    Scan(&s)
    n := len(s)
    s = " " + s
    f0, f1 := 0, int(s[1] - 'a' + 1)
    for i := 2; i <= n; i ++ {
        f2 := max(f1, f0 + int(s[i] - 'a' + 1))
        f0, f1 = f1, f2
    }
    Println(f1)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}