არა თანმიმდევრული ელემენტების მაქსიმალური ჯამი  


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Amazon American Express Facebook Google Grave ოქსიგენის საფულე OYO ოთახები Paytm Snapchat Walmart Labs Yahoo
Array დინამიური პროგრამირება

პრობლემის განცხადება  

მოცემულია "არაერთმიმდევრული ელემენტების მაქსიმალური ჯამი" მასივი, თქვენ უნდა იპოვოთ არა თანმიმდევრული ელემენტების მაქსიმალური ჯამი. თქვენ ვერ დაამატებთ უშუალო მეზობლის ციფრებს. მაგალითად [1,3,5,6,7,8,] აქ 1, 3 მომიჯნავეა, ამიტომ მათი დამატება არ შეგვიძლია, ხოლო 6, 8 არ არის მიმდებარე, რომ მათი დამატება შეგვიძლია.

მაგალითი  

შეყვანის

4 10 8 -5 6 9 2

გამოყვანის

21

ალგორითმი  

  1. მიიღეთ ორი ცვლადი incl_sum და excl_sum ისეთი, რომ ისინი წარმოადგენენ ჯამს, რომელიც შედგება იმ ელემენტის ჩათვლით, რომელზეც თქვენ დგახართ და ჯამს ქმნის შესაბამისად ამ ელემენტის გამორიცხვით.
  2. მასივის გადაკვეთა
  3. Incl_sum– ის ინიცირება პირველი ელემენტის სახით და excl_sum– ის ნულოვანი მნიშვნელობა.
  4. თითოეული ელემენტისთვის იპოვნეთ incl_sum და excl_sum.
  5. Incl_sum უდრის მოცემული ელემენტის ჯამს და excl_sum, რადგან excl_sum გამოითვლება მიმდინარე ელემენტზე ერთი ნაკლები მაჩვენებლით.
  6. excl_sum იქნება მაქსიმალური, რაც გაირკვა 4 ნაბიჯზე.
  7. დაბოლოს, გადაკვეთის შემდეგ პასუხი იქნება მაქსიმუმ ჩათვლილი და ჯამური.

განმარტება თანმიმდევრული ელემენტების მაქსიმალური ჯამის მოსაძებნად  

შეყვანის

6, 12, 10, 26, 20

მოცემულ მასივზე ალგორითმის გამოყენება,

inc = 6
ექს = 0

ნაბიჯი 1

I = 1-ისთვის (ამჟამინდელი ელემენტია 12)
max_till_now = max (6,0) = 6
ჩათვლით = (გარდა + arr [i]) = 12
გამოკლებული = 6

ნაბიჯი 2

I = 2-ისთვის (ამჟამინდელი ელემენტია 10)
max_till_now = max (12,6) = 12
ჩათვლით = (გარდა + arr [i]) = 16
გამოკლებული = 12

იხილეთ ასევე
იპოვნეთ ერთადერთი განმეორებადი ელემენტი 1-დან N-1-მდე

ნაბიჯი 3

I = 3-ისთვის (ამჟამინდელი ელემენტია 26)
max_till_now = max (16,12) = 16
ჩათვლით = (გარდა + arr [i]) = 38
გამოკლებული = 16

ნაბიჯი 4

I = 4-ისთვის (ამჟამინდელი ელემენტია 20)
max_till_now = max (38,16) = 38
ჩათვლით = (გარდა + arr [i]) = 36
გამოკლებული = 38
დაბოლოს პასუხი არის მაქსიმალური (38,36) = 38.

განხორციელება  

C ++ პროგრამა არასასურველი ელემენტების მაქსიმალური ჯამის მოსაძებნად

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int incl_sum = a[0],excl_sum = 0; //include first element   or exclude it
    int max_sum;
    for(int i=1;i<n;i++)
    {
      max_sum = max(incl_sum,excl_sum);
     incl_sum = excl_sum + a[i]; // excluded sum is till one before the adjacent element  
      excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
    }
    max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum); 
    cout<<max_sum;
     return 0;
}

Java პროგრამა არაერთმიდი ელემენტების მაქსიმალური ჯამის მოსაძებნად

import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.Scanner;

class 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 incl_sum = arr[0],excl_sum = 0; //include first element   or exclude it
        int max_sum;
        for(int i=1;i<n;i++)
        {
          max_sum = max(incl_sum,excl_sum);
         incl_sum = excl_sum + arr[i]; // excluded sum is till one before the adjacent element  
          excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
        }
        max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum); 
        System.out.println(max_sum);
    }
}
8
1 1 2 2 2 3 4 5 
11

სირთულის ანალიზი  

დროის სირთულე - O (N) სადაც n არის მასივის ზომა. აქ გადავხედავთ მთელ მასივს და ვიპოვით პასუხს.
კოსმოსური სირთულე - O (1) რადგან ჩვენ ვიყენებთ ზოგიერთ ცვლადს მხოლოდ ის, რაც სივრცის მუდმივ სირთულემდე მიგვიყვანს.

ლიტერატურა