这几道题是我在面试中亲身经历的，在面试滴滴的过程中，我遇到过最大子数组和；在面试阿里的过程中，我遇到过最长重复子串；在面试头条过程中，我遇到过最长无重复字符子串。

1. 最大子数组和

比如，给定一个数组，

1, -2, 3, -4, 5, 6, -7

应该输出，

11。

public static int maxSubArray(int[] arr) {        int max = Integer.MIN_VALUE;        int k = Integer.MIN_VALUE;        for (int i = 0; i < arr.length; i++) {            if(k > 0){                k += arr[i];            }else{                k = arr[i];            }            if(max < k){                max = k;            }        }        return max;    }

2. 最长重复子串

比如，给定一个字符串，

"hello, my name is chenchi. is chenchi."

应该输出，

" is chenchi."，注：空格也要算。

public static String maxRepat(String input) {        if(input == null || input.length() == 0){            return null;        }        int max = Integer.MIN_VALUE;        int k = Integer.MIN_VALUE;        int first = 0;        for (int i = 1; i < input.length(); i++) {            for (int j = 0; j < input.length() - i; j++) {                if(input.charAt(j) == input.charAt(i + j)){                    k++;                }else{                    k = 0;                }                if(k > max){                    max = k;                    first = j - k + 1;                }            }        }        return input.substring(first, first + max);    }

3. 最长无重复字符子串

题目要求：

 

public static int longestSubstring(String s) {        if (s.length() == 0) {            return 0;        }        int maxLength = 1;        List
     
       list = new ArrayList<>();        list.add(s.charAt(0));        for (int i = 1; i < s.length(); i++) {            if (list.contains(s.charAt(i))) {                int index = list.indexOf(s.charAt(i));                list = list.subList(index + 1, list.size());                list.add(s.charAt(i));                maxLength = Math.max(maxLength, list.size());            } else {                list.add(s.charAt(i));                maxLength = Math.max(maxLength, list.size());            }        }        return maxLength;    }