求连续子数组的最大和

package com.chinahrt.zyn.pango;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

	/**
	 * 一个整形数组，数组里有正数也有负数。
	 *数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组的和的最大值，要求时间复杂度为O(n)。
	 *例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，那么最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
	 * @param i
	 * @return
	 * Administrator
	 * 
	 */
	public int getMaxSum(Integer[] a){
		Integer[] b = getReplaceLeft(a);
		Integer[] c = getReplaceRight(b);
		List<Integer> list = megrenArray(c);
		list = megrenArrayStep2(list);
		return getMax(list);
	}
	
	//合并list中的数{正，负，正...负，正}（如果负数和前面正数，
	//后面正数的和比两个正数中的任意一个都大，合并这三个数）
	public List<Integer> megrenArrayStep2(List<Integer> list){
		for(int i=1;i<list.size()-1;){
			Integer m = list.get(i);
			if(m<0){
				Integer p = list.get(i-1);
				Integer n = list.get(i+1);
				if((m+p+n)>p&&(m+p+n)>n){
					list.remove(i-1);
					list.remove(i-1);
					list.remove(i-1);
					list.add(i-1, (p+m+n));
				}else{
					i+=2;
				}
			}
		}
		return list;
	}
	
	//把连续的正数求和合并，连续的负数求和合并，返回{正，负，正...负，正}的list
	public List<Integer> megrenArray(Integer[] a){
		List<Integer> list = new ArrayList<Integer>();
		for(int i:a){
			list.add(i);
		}
		for(int i=0;i<list.size()-1;){
			int b = (Integer)list.get(i);
			int c = (Integer)list.get(i+1);
			if((b>0&&c>0) || (b<0&&c<0)){
				list.remove(i);
				list.remove(i);
				list.add(i, new Integer(b+c));
			}else{
				i++;
			}
		}
		System.out.println("step1="+list);
		return list;
	}
	
	//去除左侧的所有负数
	public Integer[] getReplaceLeft(Integer[] i){
		Integer[] a;
		if(i[0]<=0){
			a = Arrays.copyOfRange(i, 1,i.length);
			return getReplaceLeft(a);
		}else{
			a = i;
			return a;
		}
		
	}
	//去除右侧的所有负数
	public Integer[] getReplaceRight(Integer[] i){
		Integer[] a;
		if(i[i.length-1]<=0){
			a = Arrays.copyOfRange(i, 0,i.length-1);
			return getReplaceRight(a);
		}else{
			a = i;
			return a;
		}
	}
	//求list中的最大值	
	private int getMax(List<Integer> list){
		int max = 0;
		for(Integer n:list){
			if(n>max){
				max = n;
			}
		}
		return max;
	}
	
	
	
	/**
	 * @param args
	 * Administrator
	 * 	 */
	public static void main(String[] args) {
		Test t = new Test();
		Integer[] a = {1, -2, 3, 10, -4, 7, 2, -5};
		System.out.println(t.getMaxSum(a));
		
	}

}