מאַקסימום קייַלעכיק סובאַררייַ סומע


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן facebook לינקעדין צוויי סיגמאַ ובער
מענגע

פּראָבלעם סטאַטעמענט

אין די מאַקסימום קייַלעכיק סובאַרראַי סומע פּראָבלעם, מיר האָבן געגעבן אַן מענגע פון ינטאַדזשערז עריינדזשד אין אַ קרייַז, געפֿינען די מאַקסימום סומע פון ​​קאָנסעקוטיווע נומערן אין די קייַלעכיק מענגע.

בייַשפּיל

אַרייַנשרייַב

אַרר [] = {13, -17, 11, 9, -4, 12, -1}

רעזולטאַט

40

דערקלערונג

דאָ, סומע = 11 + 9 + -4 + 12 + -1 + 13

אַרייַנשרייַב

אַרר [] = {7, 9, -11, -2, 2, 7, -1, 6}

רעזולטאַט

30

דערקלערונג

דאָ, סומע = 2 + 7 + -1 + 6+ 7 + 9

אַרייַנשרייַב

אַרר [] = {-17, -2, 1, -10, 2, 3, 7, 9}

רעזולטאַט

21

דערקלערונג

דאָ, סומע = 2 + 3 + 7 + 9

אַלגערידאַם פֿאַר מאַקסימום קייַלעכיק סובאַררייַ סומע

אין די מאַקסימום קייַלעכיק סאַב-שייכות פּראָבלעם, מיר האָבן צוויי באדינגונגען. דער ערשטער באַדינג איז אַז אַלע די עלעמענטן זענען אין די קאַנטיגיואַס סובאַרראַי. און די רגע צושטאַנד איז אַז עטלעכע יסודות פון די אָנהייב און עטלעכע יסודות פון די סוף פון די מענגע. פֿאַר בעסער פארשטאנד, זען די אונטן אַלגערידאַם-

1) עלעמענטן וואָס ביישטייערן צו די מאַקסימום סומע זענען עריינדזשד אַזוי אַז קיין ראַפּינג איז דאָרט. ווי אין בייַשפּיל (c)

2) עלעמענטן וואָס ביישטייערן צו די מאַקסימום סומע זענען עריינדזשד אַזוי אַז ראַפּינג איז דאָרט. ווי אין בייַשפּיל (a, b).

3) פֿאַר פאַל 1, מיר נוצן די סטאַנדאַרט Kadane אַלגערידאַם צו געפֿינען די מאַקסימום סאַבאַריי סאַכאַקל.

4) אין פאַל 2 מיר טוישן ראַפּינג צו ניט-ראַפּינג.

  • מיר קראָם די סומע פון ​​אַלע עלעמענטן אין דעם מענגע.
  • טוישן די צייכן פון אַלע עלעמענטן בשעת לייגן אין די סומע.
  • פֿאַר די נייַע מענגע מיט ינווערטיד וואונדער, נוצן Kadane אַלגערידאַם ווידער אויף דעם נייַע מענגע.
  • לייג די גאַנץ סומע מיט די נייַע סומע.
  • פאַרגלייכן דעם סומע מיט די ערשטע קאַדאַנע סאַכאַקל (איידער ינווערטינג די וואונדער) מאַקסימום צווישן זיי.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם פֿאַר מאַקסימום קייַלעכיק סובאַררייַ סומע

#include <bits/stdc++.h>
using namespace std;
// Standard Kadane's algorithm to find maximum subarray sum
int kadane(int array[], int n)
{
    int max_so_far = 0, max_ending_here = 0;
    for (int i = 0; i < n; i++)
    {
        max_ending_here = max_ending_here + array[i];
        if (max_ending_here < 0)
            max_ending_here = 0;
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    return max_so_far;
}
 
//function to find maximum circular subarray sum
int MaxSumCircular(int array[], int n)
{
    //Max subarray sum in the given array
    int kadane_sum = kadane(array, n);
    //wrap_sum is sum of all elements in the array
    int wrap_sum = 0;
    //find sum of all elements in the array
    //invert signs of all elements in the array
    for (int i=0; i<n; i++)
    {
        wrap_sum += array[i]; 
        array[i] = -array[i];
    }
    //update wrap_sum by add to new Max subarray sum
    wrap_sum = wrap_sum + kadane(array, n);
    //Return the maximum of them
    if(wrap_sum > kadane_sum)
    {
      return wrap_sum;
    }
    else
    {
      return kadane_sum;
    }
}
  
//Main function
int main()
{
    int input_array[] = {7, 9, -11, -2, 2, 7, -1, 6};
    int size = sizeof(input_array)/sizeof(int);
    cout<<"Maximum circular subarray sum: "<<MaxSumCircular(input_array,size)<<endl;
    return 0;
}

Java פּראָגראַם פֿאַר מאַקסימום קייַלעכיק סאַבאַריי סאַם

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int kadane(int array[], int n)
    {
        int max_so_far = 0, max_ending_here = 0;
        for (int i = 0; i < n; i++)
        {
            max_ending_here = max_ending_here + array[i];
            if (max_ending_here < 0)
                max_ending_here = 0;
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
    public static int MaxSumCircular(int array[], int n)
    {
        //Max subarray sum in the given array
        int kadane_sum = kadane(array, n);
        //wrap_sum is sum of all elements in the array
        int wrap_sum = 0;
        //find sum of all elements in the array
        //invert signs of all elements in the array
        for (int i=0; i<n; i++)
        {
            wrap_sum += array[i]; 
            array[i] = -array[i];
        }
        //update wrap_sum by add to new Max subarray sum
        wrap_sum = wrap_sum + kadane(array, n);
        //Return the maximum of them
        if(wrap_sum > kadane_sum)
        {
          return wrap_sum;
        }
        else
        {
          return kadane_sum;
        }
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = MaxSumCircular(arr,n);
        System.out.println("Maximum circular subarray sum: " + ans);
    } 
}
8
7 9 -11 -2 2 7 -1 6
Maximum circular subarray sum: 30

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N) וווּ N איז די נומער פון עלעמענטן וואָס זענען פאָרשטעלן אין די געגעבן מענגע. דאָ מיר נוצן די Kadane אַלגערידאַם וואָס פירט אונדז צו לינעאַר צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אָ (1) ווייַל מיר רעכענען די רעזולטאַט מיט אַ ביסל וועריאַבאַלז. דאָ מיר נוצן די אָפּטימאַל אַלגערידאַם אָרט קאַדאַנע.

רעפֿערענצן