一个数组的最大子串和

分手后的思念是犯贱 2022-05-20 02:04 80阅读 0赞

给出一个int类型的数组，如

-2,-4,-7,-20,1,1,1,1,-10,1,1,1,5,-10,10,10,10,-25,10,10,10,10,10,10,-300

这个数组的每个子串值相比较，很明显，最大的是由 10 10 10 -25 10 10 10 10 10 10组成的值为65的值。然后我们有两种方法具体实现，

第一种，它是O（n2）方级的，这种就和九九乘法表一样，用第一个子串去挨个的与其他的子串求和，然后在用第二个子串与剩余的子串求和，以此类推，然后在比较出来最大的那个值是多少，子串是多少，这种虽然想起来很简单，但是计算机实现就不是很简单了，我们以计算机性能为准，双层的for循环算法的计算机性能是不如一层for循环的计算机性能好的。下面我们来具体讲讲第二种：

第二种，我们以图来实现

![70][]

![70 1][]![70 2][]![70 3][]![70 4][]![70 5][]![70 6][]

具体过程已经实现，接下来我们分别用代码实现两种算法：

tatic int max(int num[]) { int maxValue = -1000; int maxNum; for(int i = 0 ;i < num.length ; i++) { maxNum = num[i]; if(maxValue < maxNum) { maxValue = maxNum; } for(int j=i+1 ; j < num.length ; j++ ) { maxNum += num[j]; if(maxValue < maxNum) { maxValue = maxNum; } } } return maxValue; }

第二种：

static String getMax(int[] num) { int maxValue = num[0]; int sum = num[0]; String sumString = "" + num[0]; String maxString = "" ; if( sum <= 0 ) sum = 0; for(int i = 1 ; i < num.length ; i++) { sum += num[i]; sumString += " " + num[i]; if( sum > maxValue ) { maxValue = sum; maxString = sumString; } if( sum < 0 ) { sum = 0; sumString = ""; } } return maxString; }

这时实现字符串的方法，删减一下，就是具体值的方法;

static int getMax(int[] num) { int maxValue = num[0]; int sum = num[0]; for(int i = 1 ; i < num.length ; i++) { sum += num[i]; if( sum > maxValue ) { maxValue = sum; } if( sum < 0 ) { sum = 0; } } return maxValue; }

[70]: /images/20220520/f623f63be6b645c4ac48a215604e0038.png
[70 1]: https://img-blog.csdn.net/20180710185212820?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTg2Njkw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180710185218741?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTg2Njkw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: https://img-blog.csdn.net/20180710185223716?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTg2Njkw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: https://img-blog.csdn.net/20180710185229996?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTg2Njkw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 5]: https://img-blog.csdn.net/20180710185236194?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTg2Njkw/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 6]: /images/20220520/4282518e647a4cc0aa2428d93dd4c06a.png