题解 | #环形数组的连续子数组最大和#
环形数组的连续子数组最大和
https://www.nowcoder.com/practice/53a9f1ba687440cc9c641c2b042a59d7
public class Main{
private static int fun(int[] nums,int n){
int[] maxs=new int[nums.length]; //记录当前下标时子序列最大和
int[] mins=new int[nums.length]; //记录当前下标时子序列最小和
int max=nums[0];int min=nums[0]; //max为不使用环形数组下最大和
maxs[0]=nums[0];mins[0]=nums[0];
for(int i=1;i<nums.length;i++){
maxs[i]=Math.max(maxs[i-1]+nums[i],nums[i]);
mins[i]=Math.min(mins[i-1]+nums[i],nums[i]);
max=Math.max(max,maxs[i]);
min=Math.min(min,mins[i]);
}
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
//sum-min使用环型数组最大和的情况下的最大和
if(sum-min==0){ //nums全为负数得到情况
return max;
}else{
return Math.max((sum-min),max);
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int[] nums=new int[sc.nextInt()];
for(int i=0;i<nums.length;i++){
nums[i]=sc.nextInt();
}
System.out.println(fun(nums,nums.length));
}
}
