java - 查找最大子数组的开始和结束索引

 public static void main(String[] args) {


        int arr[]= {0,-1,2,-3,5,9,-5,10};



        int max_ending_here=0;
        int max_so_far=0;
        int start =0;
        int end=0;

        for(int i=0;i< arr.length;i++)
        {
            max_ending_here=max_ending_here+arr[i];
            if(max_ending_here<0)
            {
                max_ending_here=0;
            }

            if(max_so_far<max_ending_here){

                max_so_far=max_ending_here;


            }

        }
        System.out.println(max_so_far);



    }

}

此程序使用{5,9，-5,10}生成子数组..在这种情况下为19的最大和。
现在我必须找到此子数组的开始和结束索引..我该怎么做??

最佳答案

像这样

public static void main(String[] args) {

    int arr[]= {0,-1,2,-3,5,9,-5,10};

    int max_ending_here=0;
    int max_so_far=0;
    int start =0;
    int end=0;


    for(int i=0;i< arr.length;i++){
        max_ending_here=max_ending_here+arr[i];
        if(max_ending_here<0)
        {
            start=i+1; //Every time it goes negative start from next index
            max_ending_here=0;
        }
        else
            end =i; //As long as its positive keep updating the end

        if(max_so_far<max_ending_here){
            max_so_far=max_ending_here;
        }

    }
    System.out.println(max_so_far);
}

好的，上面提到的解决方案存在一个问题，如St​​eve P所指出的。

public static int[] compareSub(int arr[]){
    int start=-1;
    int end=-1;
    int max=0;
    if(arr.length>0){
        //Get that many array elements and compare all of them.
        //Then compare their max to the overall max
        start=0;end=0;max=arr[0];
        for(int arrSize=1;arrSize<arr.length;arrSize++){
            for(int i=0;i<arr.length-arrSize+1;i++){
                int potentialMax=sumOfSub(arr,i,i+arrSize);
                if(potentialMax>max){
                    max=potentialMax;
                    start=i;
                    end=i+arrSize-1;
                }
            }
        }

    }
    return new int[]{start,end,max};
}

public static int sumOfSub(int arr[],int start,int end){
    int sum=0;
    for(int i=start;i<end;i++)
        sum+=arr[i];
    return sum;
}