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

finding the start and end index for a max sub array

提问by user1896796

 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);



    }

}

this program generates the max sum of sub array ..in this case its 19,using {5,9,-5,10}.. now i have to find the start and end index of this sub array ..how do i do that ??

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

采纳答案by cjds

Like This

像这样

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);
}

Okay so there was a problem in the above solution as pointed to Steve P. This is another solution which should work for all

好的，上面的解决方案中存在一个问题，正如史蒂夫 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;
}

回答by Kishore Kumar

This is a C program to solve this problem. I think logic is same for all languages so I posted this answer.

这是一个解决这个问题的C程序。我认为所有语言的逻辑都是一样的，所以我发布了这个答案。

void findMaxSubArrayIndex(){          
        int n,*a;
        int start=0,end=0,curr_max=0,prev_max=0,start_o=0,i;

        scanf("%d",&n);
        a = (int*)malloc(sizeof(int)*n);
        for(i=0; i<n; i++)  scanf("%d",a+i);

        prev_max = a[0];

        for(i=0; i<n; i++){
            curr_max += a[i];
            if(curr_max < 0){
                start = i+1;
                curr_max = 0;
            }
            else if(curr_max > prev_max){
                end = i;
                start_o = start;
                prev_max = curr_max;
            }

        }

        printf("%d %d \n",start_o,end); 
}

回答by Saurabh Jain

Here is algorithm for maxsubarray:

这是 maxsubarray 的算法：

public class MaxSubArray {

public static void main(String[] args) {
    int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
    //int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
    //int[] intArr={-6,-2,-3,-4,-1,-5,-5};
    findMaxSubArray(intArr);
}

public static void findMaxSubArray(int[] inputArray){

    int maxStartIndex=0;
    int maxEndIndex=0;
    int maxSum = Integer.MIN_VALUE; 

    int cumulativeSum= 0;
    int maxStartIndexUntilNow=0;

    for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {

        int eachArrayItem = inputArray[currentIndex];

        cumulativeSum+=eachArrayItem;

        if(cumulativeSum>maxSum){
            maxSum = cumulativeSum;
            maxStartIndex=maxStartIndexUntilNow;
            maxEndIndex = currentIndex;
        }
        if (cumulativeSum<0){
            maxStartIndexUntilNow=currentIndex+1;
            cumulativeSum=0;
        }
    }

    System.out.println("Max sum         : "+maxSum);
    System.out.println("Max start index : "+maxStartIndex);
    System.out.println("Max end index   : "+maxEndIndex);
}

}

回答by Lem0n

Fixing Carl Saldanha solution:

修复 Carl Saldanha 解决方案：

    int max_ending_here = 0;
    int max_so_far = 0;
    int _start = 0;
    int start = 0;
    int end = -1;

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

        if (max_ending_here > max_so_far) {
            max_so_far = max_ending_here;
            start = _start;
            end = i;
        }
    }

回答by sysuser

Here is a solution in python - Kadane's algorithmextended to print the start/end indexes

这是python中的一个解决方案——Kadane的算法扩展到打印开始/结束索引

def max_subarray(array):
    max_so_far = max_ending_here = array[0]
    start_index = 0
    end_index = 0
    for i in range(1, len(array) -1):
        temp_start_index = temp_end_index = None
        if array[i] > (max_ending_here + array[i]):
            temp_start_index = temp_end_index = i
            max_ending_here = array[i]
        else:
            temp_end_index = i
            max_ending_here = max_ending_here + array[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
            if temp_start_index != None:
                start_index = temp_start_index
            end_index = i
    print max_so_far, start_index, end_index

if __name__ == "__main__":
    array = [-2, 1, -3, 4, -1, 2, 1, 8, -5, 4]
    max_subarray(array)

回答by Dan

The question is somewhat unclear but I'm guessing a "sub-array" is half the arr object.

这个问题有点不清楚，但我猜“子数组”是 arr 对象的一半。

A lame way to do this like this

像这样这样做的蹩脚方法

public int sum(int[] arr){
    int total = 0;
    for(int index : arr){
        total += index;
    }
    return total;
}

public void foo(){
    int arr[] = {0,-1,2,-3,5,9,-5,10};
    int subArr1[] = new int[(arr.length/2)];
    int subArr2[] = new int[(arr.length/2)];

    for(int i = 0; i < arr.length/2; i++){
    // Lazy hack, might want to double check this...
         subArr1[i] = arr[i];
         subArr2[i] = arr[((arr.length -1) -i)];
    }

    int sumArr1 = sum(subArr1);
    int sumArr2 = sum(subArr2);
}

I image this might not work if the arr contains an odd number of elements.

我认为如果 arr 包含奇数个元素，这可能不起作用。

If you want access to a higher level of support convert the primvate arrays to a List object

如果您想获得更高级别的支持，请将 primvate 数组转换为 List 对象

List<Integer> list = Arrays.asList(arr);

This way you have access to a collection object functionality.

这样您就可以访问集合对象功能。

Also if you have the time, take a look at the higher order functional called reduce. You will need a library that supports functional programming. Guava or lambdaJ might have a reduce method. I know that apache-commons lacks one, unless you want to hack to together it.

另外，如果您有时间，请查看称为 reduce 的高阶函数。您将需要一个支持函数式编程的库。Guava 或 lambdaJ 可能有一个 reduce 方法。我知道 apache-commons 缺少一个，除非你想一起破解它。

回答by Om Prasad Nayak

In python solving 3 problem i.e., sum, array elements and index.

在python中解决3个问题，即总和、数组元素和索引。

def max_sum_subarray(arr):

    current_sum = arr[0] 
    max_sum = arr[0]     

    curr_array = [arr[0]]
    final_array=[]
    s = 0
    start = 0
    e = 0
    end = 0

    for i in range(1,len(arr)):

        element = arr[i]

        if current_sum+element > element:
            curr_array.append(element)
            current_sum = current_sum+element
            e += 1
        else:
            curr_array = [element]
            current_sum = element
            s = i

        if current_sum > max_sum:
            final_array = curr_array[:]
            start = s
            end = e
            max_sum = current_sum

    print("Original given array is : ", arr)
    print("The array elements that are included in the sum are : ",final_array)
    print("The starting and ending index are {} and {} respectively.".format(start, end))
    print("The maximum sum is : ", max_sum)

# Driver code
arr = [-12, 15, -13, 14, -1, 2, 1, -5, 4]
max_sum_subarray(arr)

• By Om Prasad Nayak

• 奥姆·普拉萨德·纳亚克 (Om Prasad Nayak)

回答by K. Ali

Here is a solution in Go using Kadane's Algorithm

这是 Go 中使用 Kadane 算法的解决方案

func maxSubArr(A []int) (int, int, int) {
    start, currStart, end, maxSum := 0, 0, 0, A[0]
    maxAtI := A[0]
    for i := 1; i < len(A); i++ {
        if maxAtI > 0 {
            maxAtI += A[i]

        } else {
            maxAtI = A[i]
            currStart = i
        }
        if maxAtI > maxSum {
            maxSum = maxAtI
            start = currStart
            end = i
        }
    }
    return start, end, maxSum
}

回答by koshyg

Here is a C++ solution.

这是一个 C++ 解决方案。

void maxSubArraySum(int *a, int size) {
    int local_max = a[0];
    int global_max = a[0];
    int sum_so_far = a[0];
    int start = 0, end = 0;
    int tmp_start = 0;
    for (int i = 1; i < size; i++) {
        sum_so_far = a[i] + local_max;
        if (sum_so_far > a[i]) {
            local_max = sum_so_far;
        } else {
            tmp_start = i;
            local_max = a[i];
        }
        if (global_max < local_max) {
            global_max = local_max;
            start = tmp_start;
            end = i;
        }
    }
    cout<<"Start Index: "<<start<<endl;
    cout<<"End Index: "<<end<<endl;
    cout<<"Maximum Sum: "<<global_max<<endl;
}

int main() {
    int arr[] = {4, -3, -2, 2, 3, 1, -2, -3, 4,2, -6, -3, -1, 3, 1, 2};
    maxSubArraySum(arr, sizeof(arr)/sizeof(arr[0]));
    return 0;
}

回答by Dipayan

An O(n) solution in C would be :-

C 中的 O(n) 解决方案将是：-

void maxsumindex(int arr[], int len)
{
    int maxsum = INT_MIN, cur_sum = 0, start=0, end=0, max = INT_MIN, maxp = -1, flag = 0;
    for(int i=0;i<len;i++)
    {
        if(max < arr[i]){
            max = arr[i];
            maxp = i;
        }
        cur_sum += arr[i];
        if(cur_sum < 0)
        {
            cur_sum = 0;
            start = i+1;
        }
        else flag = 1;
        if(maxsum < cur_sum)
        {
            maxsum = cur_sum;
            end = i;
        }
    }
    //This is the case when all elements are negative
    if(flag == 0)
    {
        printf("Max sum subarray = {%d}\n",arr[maxp]);
        return;
    }
    printf("Max sum subarray = {");
    for(int i=start;i<=end;i++)
        printf("%d ",arr[i]);
    printf("}\n");
}

回答by Kartik

    public void MaxSubArray(int[] arr)
    {
        int MaxSoFar = 0;
        int CurrentMax = 0;
        int ActualStart=0,TempStart=0,End = 0;

        for(int i =0 ; i<arr.Length;i++)
        {
            CurrentMax += arr[i];
            if(CurrentMax<0)
            {
                CurrentMax = 0;
                TempStart = i + 1;
            }
            if(MaxSoFar<CurrentMax)
            {
                MaxSoFar = CurrentMax;
                ActualStart = TempStart;
                End = i;
            }
        }
        Console.WriteLine(ActualStart.ToString()+End.ToString());
    }