最大连续子列和问题(2)

作为之前问题的升级版，我们现在不仅需要求出最大子列和，而且需要返回该结果的起始和结束下标，因为最大子列和结果不唯一，我们需要返回最小的下标。

比如输入-10 1 2 3 4 -5 -23 3 7 -21
最大子列和是10,子列和为10的子列有1,4和7,8.那我们返回"10 1 4"。如果数组中所有的数都为负数，那么返回"0 0 结束Index"。

我们仍然使用在线处理的算法，因为和结果不唯一并且需要找到最小起始下标的那一组，我们只要倒序遍历即可，算法复杂度仍然是O(n)

    public String findMaxSubsequenceSum(int[] request){
        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE;
        int step = 0;
        int endIndex = 0;
        int startIndex = 0;
        boolean allNegtive = true;
        for (int i = request.length - 1; i >= 0; i--) {
            if(request[i] > 0){
                allNegtive = false;
            }
            currentSum += request[i];
            if(currentSum < 0){
                currentSum = 0;
                step = 0;
            }else{
                step ++;
            }
            if(maxSum <= currentSum){
                maxSum = currentSum;
                startIndex = i;
                endIndex = startIndex + step - 1;
            }
        }
        return allNegtive ? "0 0 " + (request.length - 1) : maxSum + " " + startIndex + " " + endIndex;
    }