package com.bxh.array;
import java.util.ArrayList;
import java.util.Arrays;
public class findMaxMin {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,-2,4,8,-4,7,-1,-5};
// findMaxMinS(arr);
// int smax=secondMax1(arr);
// System.out.println(smax);
ArrayList<Integer> list =new ArrayList<Integer>();
list=maxSubArray(arr);
for (Integer integer : list) {
System.out.print(integer+" ");
}
System.out.println("===========================");
int sumM=maxSubArray2(arr);
System.out.println("子数组最大和为："+sumM);
}
//动态规划方法求数组中最大子数组之和
private static int maxSubArray2(int[] arr) {
// TODO Auto-generated method stub
int n=arr.length;
int [] end=new int[n];
int [] all=new int[n];
end[n-1]=arr[n-1];
all[n-1]=arr[n-1];
end[0]=all[0]=arr[0];
for(int i=1;i<n;++i){
end[i]=max(end[i-1]+arr[i],arr[i]);
all[i]=max(end[i],all[i-1]);
}
return all[n-1];
}
//两个数中比较大的数
private static int max(int m,int n) {
return m>n?m:n;
}
//求数组中最大和最大的子数组；
private static ArrayList<Integer> maxSubArray(int[] arr) {
int n=arr.length;
int sum=0,maxSum=0,i,j,k;
ArrayList<Integer> list =new ArrayList<Integer>();
for(i=0;i<n;i++){
for(j=i;j<n;j++){
sum=0;
for(k=i;k<j;k++){
sum+=arr[k];
}
if(sum>maxSum){
list.clear();
maxSum=sum;
for(k=i;k<j;k++){
list.add(arr[k]);
}
}
}
}
return list;
}
//求数组中第二大整数方法一：
private static int secondMax(int[] arr) {
// TODO Auto-generated method stub
int len=arr.length;
int smax=arr[0];
int max=arr[0];
if(max<arr[1]){
smax=max;
max=arr[1];
}else{
smax=arr[1];
}
for (int i = 2; i < arr.length; i++) {
if(arr[i]>max){
smax=max;
max=arr[i];
}else{
if(arr[i]>smax){
smax=arr[i];
}
}
}
return smax;
}
//求数组中第二大整数方法二：
private static int secondMax1(int[] arr) {
Arrays.sort(arr);
return arr[arr.length-2];
}
//求数组中最大和最小的两个数
private static void findMaxMinS(int[] arr) {
int len=arr.length;
int max=arr[0];
int min=arr[0];
for (int i = 0; i < len; i=i+2) {
if(i+1==len){
if(max<arr[i]){
max=arr[i];
}
if(min>arr[i]){
min=arr[i];
}
}
if(i+1<len && arr[i]>arr[i+1]){
if(arr[i]>max){
max=arr[i];
}
if(min>arr[i+1]){
min=arr[i+1];
}
}
if(i+1<len && arr[i]<arr[i+1]){
if(arr[i+1]>max){
max=arr[i+1];
}
if(min>arr[i]){
min=arr[i];
}
}
}
System.out.println(max+" "+min);
}
}
