题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 $O(n)$。

我们假设使用 $f(i)$ 表示以第 $i$ 个数字结尾的子数组的最大和，那么 $f(i +1)$ 与 $f(i)$ 的关系为

$$ f(i) = \begin{cases} f(i - 1) + data[i], & f(i - 1) > 0 \\ data[i], & f(i) \leq 0 \end{cases} $$

如果 $f(i - 1)$ 小于 $0$ 的话，那么 $f(i - 1) + data[i] < data[i]$，所以以第 $i$ 个数字结尾的数组最大和为 $data[i]$。我们最终的目标是寻找 $max [ f(i) ], i = 0, 1, …, n - 1$，所以代码如下

public static int findGreastSumOfSubArray(int[] data) {
    if (data == null || data.length == 0) {
        throw new RuntimeException("数组为空或null");
    }
    // f(i)
    int sum = 0;
    // max{f(i)}
    int greastSum = sum;
    // 遍历数组
    for (int i = 0; i < data.length; i++) {
        if (sum <= 0) {
            sum = data[i];
        } else {
            sum += data[i];
        }
        // 更新 max{f(i)}
        if (sum > greastSum) {
            greastSum = sum;
        }
    }
    return greastSum;
}

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含 'a'~'z' 的字符。例如，在字符串 "arabcacfr" 中，最长的不含重复字符的子字符串是 "acfr"，长度为 $4$。

我们定义 $f(i)$ 表示以第 $i$ 个字符结尾的不包含重复字符的子字符串的最长长度，那么 $f(i)$ 与 $f(i - 1)$ 的关系是什么呢?

  1. 第 $i$ 个字符从来没有出现过，那么 $f(i) = f(i - 1) + 1$
  2. 第 $i$ 个字符以前出现过，这个时候要分两种情况考虑
    • 以前出现过的字符在以 $f(i - 1)$ 表示的子字符串之中，记这两个重复的字符间的距离为 $d$，并且满足 $d \leq f(i - 1)$，这时 $f(i)$ 就是 $d$
    • 如果以前出现的字符在 $f(i - 1)$ 表示的子字符串以外，那么该字符对于 $f(i)$ 来说还是未重复的，所以 $f(i) = f(i - 1) + 1$

代码如下

public static int getLongestStringWithoutDuplication(String string) {
    if (string == null || string.length() == 0) {
        return 0;
    }
    
    char[] str = string.toCharArray();
    // 保存字符之前出现过的位置，初始为 -1，表示未出现过
    int[] position = new int[26];
    for (int i = 0; i < 26; i++) {
        position[i] = -1;
    }
    
    // f(i)
    int curLength = 0;
    // max{f(i)}
    int maxLength = 0;
    
    for (int i = 0; i < str.length; i++) {
        int prevIndex = position[str[i] - 'a'];
        // 如果之前未出现过或者 d > f(i - 1)，那么 f(i) = f(i -1) + 1
        if (prevIndex < 0 || (i - prevIndex) > curLength) {
            curLength++;
        } else {
            // 如果 f(i) 大于当前的 max{f(i)}，那么更新 max{f(i)}
            if (curLength > maxLength) {
                maxLength = curLength;
            }
            // d < f(i - 1) 时，f(i) = d = i - preIndex
            curLength = i - prevIndex;
        }
        // 设置字符出现的位置
        position[str[i] - 'a'] = i;
    }
    if (curLength > maxLength) {
        maxLength = curLength;
    }
    return maxLength;
}