Поиск начального и конечного индекса для макс.

Ответ 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;
}

Ответ 2

Это программа для решения этой проблемы. Я думаю, что логика одинакова для всех языков, поэтому я опубликовал этот ответ.

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

Ответ 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);
}

}

Ответ 4

Фиксация решения Карла Салданхи:

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

Ответ 5

Вопрос несколько неясен, но я предполагаю, что "sub-array" - это половина объекта 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);

Таким образом, у вас есть доступ к функциональности объекта коллекции.

Также, если у вас есть время, посмотрите на функционал более высокого порядка, называемый сокращением. Вам понадобится библиотека, которая поддерживает функциональное программирование. Guava или lambdaJ могут иметь метод уменьшения. Я знаю, что apache-commons не хватает одного, если вы не хотите взломать его вместе.

Ответ 6

Вот решение в python - алгоритм Кадана, расширенный для печати индексов начала и конца

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)

Ответ 7

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

Ответ 8

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

Ответ 9

Единственное, что я должен добавить (к нескольким решениям, размещенным здесь), - это охватить случай, когда все целые числа отрицательны, и в этом случае максимальный вспомогательный массив будет всего лишь максимальным элементом. Довольно легко сделать это. Просто нужно отслеживать максимальный элемент и индекс индекса элемента max при его повторении. Если максимальный элемент отрицательный, верните его вместо этого.

Существует также случай переполнения, который возможно обрабатывается. Я видел тесты алгоритмов, которые принимают, а не учет. IE, предположим, что MAXINT был одним из элементов, и вы пытались добавить к нему. Я считаю, что некоторые из тестов Codility (скрининга на тестирование кодирования) учитывают это.

Ответ 10

Решение O (n) в C было бы: -

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

Ответ 11

Вот решение в 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
}