首页 / JAVA / 求最大子串和 最长子串的java写法
求最大子串和 最长子串的java写法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了求最大子串和 最长子串的java写法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2815字，纯文字阅读大概需要5分钟。
内容图文
同事去面试问到求最大和的子串，举例来说给你一个有正有负的数组， 1 -1 2 -4 5 6 -3，它的最大和就是 5 6 所组成的子串和11。根据其隔离性，即任何子串内部都不会有这样一个结构 2 -4，因为如果包含这个子串，必定不是最大子串（2-4<0）,因此可以根据此性质，将数组进行分割，而分割的标志就是小于0的结构。
1
public
static
void
main(String[] args) {
2
3
int[] array = {1,2,-4,3,5,-4,7,8,2,-1,6,-5,-200,3,47,-2};
4 5 System.out.println(findMaxValue(array));
6 7//寻找最大子串 8int [] subArray = findMaxSubArray(array);
9for(int tmp : subArray){
10 System.out.print(tmp+ " ");
11 }
1213 }
1415/**16 * @Description:找到最大子串和
17 * @param array
18 * @return19 * @returType:int
20*/21publicstaticint findMaxValue(int[] array){
22int max = 0;
23int sum = 0;
24for(int i=0;i<array.length;i++){
25 sum = sum + array[i];
26if(sum > max){
27 max = sum;
2829 }elseif(sum<0){
30 sum = 0;
31 }
32 }
33return max;
34 }
3536/**37 * @Description:找到一个字符串的最大子串
38 * @param array
39 * @return40 * @returType:int[]
41*/42publicstaticint[] findMaxSubArray(int[] array){
43int max = 0;
44int sum = 0;
45int start = 0;
46int end = 0;
47int tmpStart = 0;
48for(int i=0;i<array.length;i++){
49 sum = sum + array[i];
50if(sum > max){
51 max = sum;
52 start = tmpStart;
53 end = i;
54 }elseif(sum<0){
55 sum = 0;
56 tmpStart = i;
57 }
58 }
59return Arrays.copyOfRange(array, start+1, end+1);//截取不包括自己60 }
还有一种是求，给定一个数组，求数组中最长的子串，子串的头和尾是同一个数字。例如：1，2，3，4，2，4 2的间距是3
1
public
static
void
main(String[] args) {
2
3
int[] array = {1,2,-4,3,5,-4,7,8,2,-1,6,-5,-200,3,47,-2};
4//寻找最长子串 5int[] lenArray = findMaxLengthArray(array);
6for(int tmp : lenArray){
7 System.out.print(tmp+ " ");
8 }
910 }
1112/**13 * @Description:求最长子串
14 * @param array
15 * @return16 * @returType:int[]
17*/18publicstaticint[] findMaxLengthArray(int[] array){
19//key 放置数组的元素，value 第一个元素存放起始位置，第二个放置结束位置，第三个元素存放距离20 Map<Integer, Integer[]> map = new HashMap<Integer, Integer[]>();
21for(int i=0;i<array.length;i++){
22if(map.get(array[i])==null){
23 Integer[] ints = new Integer[3];
24 ints[0]=i;//初始位置25 ints[1]=i;//结束位置26 ints[2]=0;//初始长度27 map.put(array[i], ints);
28 }else{
29 map.get(array[i])[1]=i;
30 map.get(array[i])[2]=i-map.get(array[i])[0];
31 }
32 }
33 Iterator<Entry<Integer, Integer[]>> iterator = map.entrySet().iterator();
34int max = 0;
35int start = 0;
36int end = 0;
37int key = 0;
38while(iterator.hasNext()){
39 Entry<Integer, Integer[]> entry = iterator.next();
40if(entry.getValue()[2]>max){
41 max = entry.getValue()[2];
42 start = entry.getValue()[0];
43 end = entry.getValue()[1];
44 key = entry.getKey();
45 }
46 }
47 System.out.println("最大长度的数字是："+ key);
48 System.out.println("最大长度为:"+max);
49return Arrays.copyOfRange(array, start+1, end+1);//截取不包括自己50 }
实际上使用了一个hashmap，value存储了开始位置，结束位置以及长度，因此一遍遍历数组，再一遍遍历hashmap就可以求出最长距离，Integer[] 改成hashmap效率会更高一些，时间复杂度为O(n)，空间复杂度高一些
原文：http://www.cnblogs.com/seanvon/p/4018887.html
内容总结
以上是互联网集市为您收集整理的求最大子串和 最长子串的java写法全部内容，希望文章能够帮你解决求最大子串和 最长子串的java写法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。