//最大子段和_简单解法
package wkx;
 
import java.io.IOException;
 
public class Test { 
	
	private static int MaxSum(int[] a,Point p) {
		int len =a.length;
		int sum=0;
		int max=Integer.MIN_VALUE;
		for(int i=0;i<len;i++){
			for(int j=i;j<len;j++){
				sum=0;
				for(int k=i;k<=j;k++){
					sum+=a[k];
				}
				if(sum>max){
					max=sum;
					p.x=i;
					p.y=j;
				}
			}
		}
		return max;
	}
	
	private static class Point{
		private int x;
		private int y;
	}
	
	public static void main(String[] args) throws IOException {
		int[] a=new int[]{-2,11,-4,13,-5,-2};
		Point p=new Point();
		System.out.println(MaxSum(a,p));
		System.out.println(p.x+" "+p.y);
	}
}
 
 
//最大子段和_简单解法改进
package wkx;
 
import java.io.IOException;
 
public class Test {
 
	private static int MaxSum(int[] a, Point p) {
		int len = a.length;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < len; i++) {
			int sum = 0;
			for (int j = i; j < len; j++) {
				sum += a[j];
				if (sum > max) {
					max = sum;
					p.x = i;
					p.y = j;
				}
			}
		}
		return max;
	}
 
	private static class Point {
		private int x;
		private int y;
	}
 
	public static void main(String[] args) throws IOException {
		int[] a = new int[] { -2, 11, -4, 13, -5, -2 };
		Point p = new Point();
		System.out.println(MaxSum(a, p));
		System.out.println(p.x + " " + p.y);
	}
}
 
 
//最大子段和_分治解法
package wkx;
 
import java.io.IOException;
 
public class Test {
 
	private static int MaxSum(int[] a, int beg, int end) {
		if (beg == end) {
			return a[beg];
		}
		int mid = (beg + end) / 2;
		int leftSum = MaxSum(a, beg, mid);
		int rightSum = MaxSum(a, mid + 1, end);
		int sumLeft=0;
		int left=0;
		for(int i=mid;i>=0;i--){
			left+=a[i];
			if(left>sumLeft){
				sumLeft=left;
			}
		}
		int sumRight=0;
		int right=0;
		for(int i=mid+1;i<=end;i++){
			right+=a[i];
			if(right>sumRight){
				sumRight=right;
			}
		}
		int sum=sumLeft+sumRight;
		if(sum<leftSum)
			sum=leftSum;
		if(sum<rightSum)
			sum=rightSum;
		return sum;
	}
 
	public static void main(String[] args) throws IOException {
		int[] a = new int[] { -2, 11, -4, 13, -5, -2 };
		System.out.println(MaxSum(a, 0, a.length - 1));
	}
}
 
//最大子段和_动态规划解法
package wkx;
 
import java.io.IOException;
 
public class Test {
 
	private static int MaxSum(int[] a,Point p) {
		int sum = 0, b = 0;
		for (int i = 0; i < a.length; i++) {
			if (b > 0) {
				b += a[i];
			} else {
				p.x=i;
				b = a[i];
			}
			if (b > sum) {
				p.y=i;
				sum = b;
			}
		}
		return sum;
	}
	
	private static class Point{
		private int x;
		private int y;
	}
	
	public static void main(String[] args) throws IOException {
		int[] a = new int[] { -2, 11, -4, 13, -5, -2 };
		Point p=new Point();
		System.out.println(MaxSum(a,p));
		System.out.println(p.x+" "+p.y);
	}
}