这两道题是我在面试中亲身经历的, 在面试滴滴的过程中, 我遇到过最大子数组和, 在面试阿里的过程中, 我遇到过最长重复子串.
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);
- }
来源: http://www.bubuko.com/infodetail-2722781.html