vlambda博客
学习文章列表

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

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

如果 小于 的话，那么 ，所以以第 个数字结尾的数组最大和为 。我们最终的目标是寻找 ，所以代码如下

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"，长度为 。

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

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

代码如下

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;
}