2021-12-09（JZ85 连续子数组的最大和(二)）

142 阅读 0 评论 94 点赞

我是靠谱客的博主冷艳红酒，这篇文章主要介绍2021-12-09（JZ85 连续子数组的最大和(二)），现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
int[] dp=new int[array.length];
dp[0]=array[0];
int maxLength=1,maxSum=array[0],left=0,right=0,sLeft=0,sRight=0;
for(int i=1;i<array.length;++i){
++right;
dp[i]=Math.max(array[i]+dp[i-1],array[i]);
if(array[i]+dp[i-1]<array[i])left=right;
if(dp[i]>maxSum||dp[i]==maxSum&&(right-left+1)>maxLength){
sLeft=left;
sRight=right;
maxLength=right-left+1;
maxSum=dp[i];
}
}
int[] res=new int[maxLength];
int idx=0;
for(int i=sLeft;i<=sRight;++i){
res[idx++]=array[i];
}
return res;
}
}