题解 | #环形数组连续最大和#
环形数组的连续子数组最大和
http://www.nowcoder.com/practice/53a9f1ba687440cc9c641c2b042a59d7
同时维护最大最小，全是负数的时候额外考虑一下。
import java.util.*;
public class Main{
public static void main(String []args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int []num=new int[n];
for(int i=0;i<n;i++){
num[i]=input.nextInt();
}
int [][]dp=new int[n][2];
int max=num[0];
int min=num[0];
dp[0][0]=num[0];
dp[0][1]=num[0];
for(int i=1;i<n;i++){
dp[i][0]=Math.max(dp[i-1][0]+num[i],num[i]);
dp[i][1]=Math.min(dp[i-1][1]+num[i],num[i]);
max=Math.max(max,dp[i][0]);
min=Math.min(min,dp[i][1]);
}
int sum=0;
for(int i=0;i<n;i++){
sum+=num[i];
}
if(sum-min==0){
for(int i=0;i<n;i++){
max=Math.max(max,num[i]);
}
System.out.println(max);
}
else{
System.out.println(Math.max(max,sum-min));
}
}
}
