package max.number;

public class FenZhi {

	/**
	 * 获取左边最大的字段和（连续的）
	 * @param a
	 * @return
	 */
	public static int getLeft(int[] a) {
		int left = 0, sum = 0, left_max = 0;
		int center = (a.length - 1) / 2;
		// 遍历左边
		// 获取左边的最大子段和
		for (int i = center; i >= left; i--) {
			sum += a[i];
			if (sum > left_max)
				left_max = sum;
		}
		return left_max;
	}

	/**
	 * 获取右边的子段和（连续）
	 * @param a
	 * @return
	 */
	public static int getRight(int[] a) {
		int right = a.length - 1, sum = 0, right_max = 0;
		int center = (a.length - 1) / 2;
		for (int i = center + 1; i <= right; i++) {
			sum += a[i];
			if (sum > right_max)
				right_max = sum;
		}
		return right_max;
	}

	public static void main(String[] args) {
		int[] a = { -2, 11, -4, 13, -5, -2 };
		int left_max = getLeft(a);
		int right_max = getRight(a);
		int sum = left_max + right_max;
		System.out.println("第一种情况：left_max：" + left_max);
		System.out.println("第二种情况：right_max：" + right_max);
		System.out.println("第三种情况：sum：" + sum);

	}
}

package max.number.demo3;

/**
 * 分治法
 */
public class FenZhiFa {

	/**
	 * 
	 * @param a
	 *            数组
	 * @param left
	 *            最左边
	 * @param right
	 *            最右边
	 * @return
	 */
	public static int MaxSum(int a[], int left, int right) {
		int sum = 0;
		if (left == right) {// 如果序列长度为1，则可以直接求解
			if (a[left] > 0) {
				sum = a[left];
			} else {
				sum = 0;
			}
		} else {
			int center = (left + right) / 2; // 划分
			int leftSum = MaxSum(a, left, center);// 对应情况1，即最大子段和为左边的一段，递归求解， 这里递归获取最大值，和总和的值进行比较
			int rightSum = MaxSum(a, center + 1, right);// 对应情况2，即最大子段和为右边的一段，递归求解

			int s1 = 0, lefts = 0;// 对应情况3，即最大子段和为左右两段之间的某段，先求解s1
			for (int i = center; i >= left; i--) {
				lefts += a[i];
				if (lefts > s1) {
					s1 = lefts;
				}
			}

			int s2 = 0, rights = 0;// 再求解s2
			for (int j = center + 1; j <= right; j++) {
				rights += a[j];
				if (rights > s2) {
					s2 = rights;
				}
			}
			sum = s1 + s2;// 计算第3种情况的最大子段和
			if (sum < leftSum) {
				sum = leftSum;
			}
			if (sum < rightSum) {
				sum = rightSum;
			}// 在这三种情况中选择较大者
		}
		return sum;
	}

	public static void main(String[] args) {
		int[] a = { -2, 11, -4, 13, -5, -2 };
		int SUM = MaxSum(a, 0, a.length - 1);
		System.out.println("最大子段和为：" + SUM);
	}
}

package max.number;

/**
 * 简单的最大子段和
 */
public class Max {

	public static void main(String[] args) {

		// int[] a = { -2, 11, -4, 13, -5, -2 };
		// 待确定的数组
		int[] a = { 1, 2, -1, 1, 3, 2, -2, 3, -1, 5, -7, 3, 2, -2, 4 - 5 };
		// 子段和的数组，选出最大的那个值
		int[] b = new int[a.length];
		b[0] = a[0];
		int max = b[0];
		for (int i = 1; i < a.length; i++) {
			if (b[i - 1] > 0) {
				b[i] = b[i - 1] + a[i];
			} else {
				b[i] = a[i];
			}
			if (max < b[i]) {
				max = b[i];
			}
		}
		System.out.println(max);
	}
}

package max.number;

/**
 * 最大子段和
 * 
 * 动态规划方法： 若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。则所求的最大子段和为max
 * b[j]，1<=j<=n。 由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。
 * 故b[j]的动态规划递归式为: b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
 * 
 * 主要有打印：最大子段数组
 * 
 * 写的不是很好
 * 
 */
public class MaxArray {

	/**
	 * 输出数组
	 * 
	 * @param a
	 */
	public static void prtArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.print("\n");
	}

	/**
	 * 2个数字最大值 返回最大值
	 * 
	 * @param a1
	 * @param a2
	 * @return
	 */
	public static int max(int a1, int a2) {
		if (a1 >= a2 || a1 == a2)
			return a1;
		return a2;
	}

	/**
	 * 设置最大B：最大字段和
	 * 
	 * a,b,beg数组长度相同
	 * 
	 * @param n
	 *            长度，数组位置下标
	 * @param b
	 * @param a
	 * @param beg
	 */
	public static void setB(int n, int[] b, int[] a, int[] beg) {
		// 下标是0
		if (n == 0) {
			b[n] = a[n];
			beg[n] = n;
		} else {
			// n递减
			setB(n - 1, b, a, beg);
			// 最大值b[n]
			b[n] = max(b[n - 1] + a[n], a[n]);
			if (b[n - 1] + a[n] > a[n])
				beg[n] = beg[n - 1];
			else
				beg[n] = n;
		}
	}

	/**
	 * 最大子数组 b[] 最大子段数组
	 * 
	 * @param a
	 */
	public static void maxChildArry(int[] a) {
		// 新建a长度的b数组
		int b[] = new int[a.length];
		// 新建最大子段和的开始的位置
		int beg[] = new int[a.length];
		// a，b数组第一位相同
		b[0] = a[0];
		// 遍历数组
		for (int n = 0; n < b.length; n++)
			setB(n, b, a, beg);
		// 最大的数字
		int maxsum = b[getMaxElementIndex(b)];
		System.out.println("MaxSum: " + maxsum);
		PrtMaxChildArry(a, beg[getMaxElementIndex(b)], getMaxElementIndex(b));
	}

	/**
	 * 打印最大子段合的子数组
	 * 
	 * @param aa
	 * @param beg
	 * @param end
	 */
	public static void PrtMaxChildArry(int aa[], int beg, int end) {
		System.out.print("The Maxmium Child-Array is: { ");
		for (int i = beg; i <= end; i++) {
			System.out.print(aa[i] + " ");
		}
		System.out.println("}\n");

	}

	/**
	 * 获取最大值子段合的最大节点下标
	 * 
	 * @param b
	 * @return
	 */
	public static int getMaxElementIndex(int[] b) {
		int maxele = 0;
		int i;
		for (i = 1; i < b.length; i++) {
			if (b[maxele] < b[i]) {
				maxele = i;
			}
		}
		return maxele;

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// int[] a = { 1, 2, -1, 1, 3, 2, -2, 3, -1, 5, -7, 3, 2, -2, 4 - 5 };
		// prtArray(a);
		int[] a = { -2, 11, -4, 13, -5, -2 };
		maxChildArry(a);
	}

}