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



    }

}

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

4

17 回答 17

10

这是一个解决这个问题的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); 
}
于 2016-06-25T00:30:57.463 回答
6

修复 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;
        }
    }
于 2014-11-29T21:42:19.063 回答
3

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

}
于 2013-10-22T10:30:20.173 回答
3

这是 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)
于 2015-09-03T09:25:11.580 回答
1

像这样

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

好的，正如 Steve 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;
}
于 2013-01-06T07:50:24.750 回答
1

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

一个蹩脚的方式来做到这一点

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

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

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

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

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

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

于 2013-01-06T08:13:26.820 回答
1

我唯一需要添加的（这里发布的几个解决方案）是涵盖所有整数都是负数的情况，在这种情况下，最大子数组将只是最大元素。很容易做到这一点.. 只需在遍历它时跟踪最大元素和最大元素索引的索引。如果最大元素为负数，则返回它的索引。

还有可能处理溢出的情况。我已经看到算法测试考虑到了.. IE，假设 MAXINT 是元素之一，而你试图添加到它。我相信一些 Codility（编码面试筛选器）测试会考虑到这一点。

于 2015-03-25T18:13:59.610 回答
1

在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)
  • 奥姆·普拉萨德·纳亚克
于 2020-05-11T14:42:04.360 回答
0 
public static void maxSubArray(int []arr){
    int sum=0,j=0;
    int temp[] = new int[arr.length]; 

    for(int i=0;i<arr.length;i++,j++){  
        sum  =  sum + arr[i];
        if(sum <= 0){
            sum =0;
            temp[j] = -1;
        }else{              
            temp[j] = i;                
        }
    }
    rollback(temp,arr);
}

public static void rollback(int [] temp , int[] arr){
    int s =0,start=0 ;
    int maxTillNow = 0,count =0;
    String str1 = "",str2="";
    System.out.println("============");
    // find the continuos index 
    for(int i=0;i<temp.length;i++){

        if(temp[i] != -1){
            s += arr[temp[i]];  
            if(s > maxTillNow){
                if(count == 0){
                    str1 = "" + start;
                }
                count++;
                maxTillNow = s;
                     str2 =  " " + temp[i]; 
            }
        }else{
            s=0;
            count =0;
            if(i != temp.length-1)
                start = temp[i+1];
        }

    }
    System.out.println("Max sum will be  ==== >> " + maxTillNow);
    System.out.print("start from ---> "+str1 + "  end to --- >>  " +str2);
}
于 2014-07-15T10:44:25.817 回答
0 
    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());
    }
于 2014-12-19T07:18:02.490 回答
0

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");
}
于 2016-03-01T00:27:20.813 回答
0

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

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
}
于 2018-12-27T00:46:49.153 回答
0

这是一个 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;
}
于 2019-11-19T07:14:04.013 回答
0 
pair<int,int> maxSumPair(vector<int> arr) {
int n = arr.size();`
int currSum = arr[0], maxSoFar = arr[0];
int start = 0, end ,prev = currSum;
    unordered_map<int,pair<int,int>> mp;
    for(int i = 1 ; i < n ; i++) {
        prev = currSum;
        if(currSum == arr[i]) {
            end = i-1;
            mp.insert({currSum,{start,end}});
            start = i;
        }
        if(maxSoFar < currSum) {
            maxSoFar = currSum;
            end = i;
            mp.insert({currSum,{start,end}});
        }
    }
    int maxSum = INT_MIN;
    for(auto it: mp) {
        if(it.first > maxSum) {
            maxSum = it.first;
        }
    }
    return mp[maxSum];
}
于 2021-04-24T07:26:01.130 回答
0

int maxSubarraySum(int arr[], int n){

    int max_so_far = -1 * Integer.MAX_VALUE;
    int max_curr = 0;
    int start = 0;
    int end = 0;
    
    for(int i=0; i < arr.length; i++){
        max_curr = max_curr + arr[i];
        if(max_so_far < max_curr){
            max_so_far = max_curr;
        }
        
        if( max_curr < 0){
          max_curr = 0;
          start = i+1;
        }
        else 
        end = i;
    }
    
    start = end < start ? end : start;
    System.out.println( start + "..." + end);
    return max_so_far;
}
于 2021-08-18T16:46:28.747 回答
0

golang实现中的最大子数组

package main

import (
    "fmt"
)

func main() {
    in := []int{-2, -12, 23, -10, 11, -6, -1}
    a, b := max(in)
    fmt.Println(a)
    fmt.Println(b)
}

func max(in []int) ([]int, int) {
    var p, r, sum, sf, psf int
    if len(in) == 0 {
        return in, 0
    }

    sum = in[0]

    for i, n := range in {
        sf += n
        if sf > sum {
            sum = sf
            p = psf
            r = i
        }

        if sf <= 0 {
            psf = i + 1
            sf = 0
        }
    }
    return in[p : r+1], sum
}
于 2021-11-04T05:57:07.600 回答
0

我认为这将有助于获取开始和结束索引

// Time Complexity = O(N)
// Space Complexity = O(1)
public static int maxSum2(int[] nums){
    int globalSum = Integer.MIN_VALUE;
    int currentSum = 0;
    int start=0;
    int end=0;
    for(int i=0; i<nums.length;i++){
        currentSum += nums[i];
        if (currentSum>globalSum){
            globalSum = currentSum;
            end = i;
        }
        if (currentSum<0){
            currentSum=0;
            start = i+1;
        }
    }
    System.out.println(start + " " + end);
    return globalSum;
}
于 2022-02-27T10:18:38.043 回答