找出所有连续数字之和最大的子串（java）_JAVA_编程开发_程序员俱乐部

class="java">import com.beust.jcommander.internal.Lists;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author zhongchenghui
 */
public class MaxSumConstantlyNumbers {

    public static void main(String[] args) {
        List<Integer> list = Lists.newArrayList(-1, 3, -2, 4, 5, 7, 3, -5, 3, -16, 9, 10, -12, -8, 20, -20, 12, 5, 3);
        fun(list);
    }

    public static void fun(List<Integer> list) {
        List<IndexPair> indexPairs = new ArrayList<>();
        int maxTotal = Integer.MIN_VALUE;
        int startIndex = 0;
        int endIndex = 0;
        int currentMaxTotal = 0;
        int currentIndex = 0;
        int currentTotal = 0;
        for (Integer i : list) {
            currentTotal += i;
            currentIndex++;
            if (currentTotal > 0) {
                if (currentTotal >= currentMaxTotal) {
                    endIndex = currentIndex;
                    currentMaxTotal = currentTotal;
                }
            } else {
                if (currentMaxTotal >= maxTotal) {
                    if (currentMaxTotal > maxTotal) {
                        indexPairs.clear();
                    }
                    final IndexPair indexPair = new IndexPair(startIndex, endIndex);
                    indexPairs.add(indexPair);
                    maxTotal = currentMaxTotal;
                }
                startIndex = currentIndex;
            }
        }
        if (currentMaxTotal >= maxTotal) {
            if (currentMaxTotal > maxTotal) {
                indexPairs.clear();
            }
            final IndexPair indexPair = new IndexPair(startIndex, endIndex);
            indexPairs.add(indexPair);
            maxTotal = currentMaxTotal;
        }

        for (IndexPair indexPair : indexPairs) {
            System.out.println(indexPair);
            System.out.println(list.subList(indexPair.startIndex, indexPair.endIndex));
            System.out.println();
        }
        System.out.println("最大值为：" + maxTotal);
    }

    public static class IndexPair {

        int startIndex;
        int endIndex;

        public IndexPair(int startIndex, int endIndex) {
            IndexPair.this.startIndex = startIndex;
            IndexPair.this.endIndex = endIndex;
        }

        @Override
        public String toString() {
            return "IndexPair{" + "startIndex=" + startIndex + ", endIndex=" + endIndex + '}';
        }

    }
}

?以上答案有待改进。一遍遍历之后只是找出了每个子串的起止位置，而后再根据起止位置截取子串。更好的做法是在遍历过程中就把子串保存下来。