算法基础之求子数组之和的最大值并记录下标
标题起的又一次把自己恶心到了。。
算法实现完全来源于编程之美，最简单的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 }; // 19int 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;}}