算法基础之求子数组之和的最大值并记录上标

算法基础之求子数组之和的最大值并记录下标
标题起的又一次把自己恶心到了。。
算法实现完全来源于编程之美，最简单的DP思想的实践。
maxSubSum2方法中稍作修改，记录了下该子序列的下标。

/**
 * 子数组之和的最大值：要求子数组的元素是连续的
 * 
 * @author aaron-han
 * 
 */
public class MaxSubSum {

	public static void main(String[] args) {
		int[] arr = { 3, 5, -3, -2, 5, 8, 3, -2, 1 }; // 19
		int maxSum = maxSubSum2(arr, arr.length);
		System.out.println("\n" + maxSum);
	}

	// 尾->首
	// nAll保存当前的最大子数组之和，nStart保存当前的子数组之和，初值均设为最后一个元素。
	public static int maxSubSum(int[] arr, int length) {
		int nAll = arr[length - 1];
		int nStart = arr[length - 1];
		for (int i = length - 2; i >= 0; i--) {
			if (nStart < 0) { // 若为负数，则清零重新寻找。
				nStart = 0;
			}
			nStart += arr[i];
			if (nStart > nAll) { // 若当前子数组之和大于nAll，则更新nAll。
				nAll = nStart;
			}
		}
		return nAll;
	}

	// 在遍历求值的基础上记录了子序列的index并打印
	public static int maxSubSum2(int[] arr, int length) {
		int nAll = arr[length - 1];
		int nStart = 0;
		int endIndex = length - 1;
		int startIndex = length - 1;
		int tempIndex = length - 1;
		for (int i = length - 1; i >= 0; i--) {
			if (nStart < 0) {
				nStart = 0;
				tempIndex = i;
			}
			nStart += arr[i];
			if (nStart > nAll) {
				nAll = nStart;
				endIndex = tempIndex;
				startIndex = i;
			}
		}
		for (int i = startIndex; i <= endIndex; i++) {
			System.out.print(arr[i] + "\t");
		}
		return nAll;
	}
}