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



    }

}

このプログラムは、サブ配列の最大合計を生成します..この場合、{5,9,-5,10} を使用して 19 です..このサブ配列の開始インデックスと終了インデックスを見つける必要があります..どうすればよいですかそれ ？？

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 に答える
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 に答える
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 に奇数の要素が含まれている場合、これは機能しない可能性があると思います。

より高いレベルのサポートにアクセスしたい場合は、primvate 配列を List オブジェクトに変換します

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

このようにして、コレクション オブジェクトの機能にアクセスできます。

また、時間があれば、reduce と呼ばれる高階汎関数を調べてください。関数型プログラミングをサポートするライブラリが必要になります。Guava または lambdaJ には reduce メソッドがある場合があります。一緒にハックしたくない限り、apache-commonsには1つがないことを私は知っています。

于 2013-01-06T08:13:26.820 に答える
1

（ここに投稿されたいくつかのソリューションに）追加する必要がある唯一のことは、すべての整数が負の場合をカバーすることです。この場合、最大サブ配列は最大要素になります。それを行うのは非常に簡単です..反復するときに、最大要素と最大要素のインデックスのインデックスを追跡するだけです。最大要素が負の場合、代わりにそのインデックスを返します。

場合によっては処理にオーバーフローする場合もあります。よりも考慮に入れるアルゴリズムテストを見てきました..IE、MAXINTが要素の1つであり、それに追加しようとしたとします。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

Maximum sub array in golang implementation

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 に答える