package dp;

import org.junit.Test;

import java.util.HashMap;

/**

* @Author: wei1

* @Date: Create in 2018/12/10 13:31

* @Description: 最大子串是要找出由数组成的

* 一维数组中和最大的连续子序列。比如{5,-3,4,2}

* 的最大子串就是 {5,-3,4,2}，它的和是8,达到

* 最大；而 {5,-6,4,2}的最大子串是{4,2}，它的

* 和是6。

*/

public class MaxSubSum {

class ResultType {

int start;

int end;

public ResultType() {

}

public int getStart() {

return start;

}

public void setStart(int start) {

this.start = start;

}

public int getEnd() {

return end;

}

public void setEnd(int end) {

this.end = end;

}

public ResultType(int start, int end) {

this.start = start;

this.end = end;

}

}

public int maxSubSum(int[] arr, HashMap<Integer, ResultType> map) {

int max = 0;

ResultType resultType = new ResultType();

int sum = 0;

for (int i = 0; i < arr.length; i++) {

if (arr[i] >= 0) {

if (sum == 0) {

resultType.start = i;

}

sum += arr[i];

max = max > sum ? max : sum;

} else {

if (sum >= max) {

resultType.end = i - 1;

map.put(max, new ResultType(resultType.start, resultType.end));

}

sum = 0;

}

}

if (!map.containsKey(max)) {

map.put(max, new ResultType(resultType.start, arr.length - 1));

}

return max;

}

@Test

public void test() {

HashMap<Integer, ResultType> map = new HashMap<>();

int[] arr = {5, -6, 4, 2, 0, -1, 3, -5};

int result = maxSubSum(arr, map);

System.out.println(result);

ResultType resultType = map.get(result);

for (int i = resultType.start; i <= resultType.end; i++) {

System.out.print(arr[i] + " ");

}

}

}