തുടർച്ചയായ മൂലകങ്ങളുടെ പരമാവധി തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ അമേരിക്കൻ എക്സ്പ്രസ് ഫേസ്ബുക്ക് ഗൂഗിൾ എടുക്കുക ഓക്സിജൻ വാലറ്റ് OYO മുറികൾ Paytm Snapchat വാൾമാർട്ട് ലാബുകൾ യാഹൂ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

നൽകിയിട്ടുള്ള “തുടർച്ചയായ മൂലകങ്ങളുടെ പരമാവധി തുക” ൽ ശ്രേണി, തുടർച്ചയായുള്ള ഘടകങ്ങളുടെ പരമാവധി തുക നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. നിങ്ങൾക്ക് ഉടനടി അയൽ നമ്പറുകൾ ചേർക്കാൻ കഴിയില്ല. ഉദാഹരണത്തിന് [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 നിലവിലെ മൂലകത്തിന്റെ ആകെത്തുകയ്ക്ക് തുല്യമായിരിക്കും, കൂടാതെ exl_sum നിലവിലെ മൂലകത്തേക്കാൾ ഒരു കുറവ് സൂചിക വരെ exl_sum കണക്കാക്കിയതിനാൽ.
  6. excl_sum നാലാം ഘട്ടത്തിൽ കണ്ടെത്തിയ പരമാവധി ആയിരിക്കും.
  7. അവസാനമായി, ട്രാവെർസൽ ഉത്തരത്തിന് ശേഷം പരമാവധി incl_sum, excl_sum ആയിരിക്കും.

തുടർച്ചയായ മൂലകങ്ങളുടെ പരമാവധി തുക കണ്ടെത്തുന്നതിനുള്ള വിശദീകരണം

ഇൻപുട്ട്

6, 12, 10, 26, 20

തന്നിരിക്കുന്ന അറേയിൽ അൽഗോരിതം പ്രയോഗിക്കുന്നു,

inc = 6
exc = 0

സ്റ്റെപ്പ് 1

I = 1 ന് (നിലവിലെ ഘടകം 12 ആണ്)
max_till_now = പരമാവധി (6,0) = 6
incl = (excl + arr [i]) = 12
excl = 6

സ്റ്റെപ്പ് 2

I = 2 ന് (നിലവിലെ ഘടകം 10 ആണ്)
max_till_now = പരമാവധി (12,6) = 12
incl = (excl + arr [i]) = 16
excl = 12

സ്റ്റെപ്പ് 3

I = 3 ന് (നിലവിലെ ഘടകം 26 ആണ്)
max_till_now = പരമാവധി (16,12) = 16
incl = (excl + arr [i]) = 38
excl = 16

സ്റ്റെപ്പ് 4

I = 4 ന് (നിലവിലെ ഘടകം 20 ആണ്)
max_till_now = പരമാവധി (38,16) = 38
incl = (excl + arr [i]) = 36
excl = 38
അവസാനമായി ഉത്തരം പരമാവധി (38,36) = 38.

നടപ്പിലാക്കൽ

തുടർച്ചയായ മൂലകങ്ങളുടെ പരമാവധി തുക കണ്ടെത്തുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

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

തുടർച്ചയായ മൂലകങ്ങളുടെ പരമാവധി തുക കണ്ടെത്തുന്നതിനുള്ള ജാവ പ്രോഗ്രാം

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) കാരണം ഞങ്ങൾ ചില വേരിയബിളുകൾ മാത്രമാണ് ഉപയോഗിക്കുന്നത്, അത് സ്ഥിരമായ സ്ഥല സങ്കീർണ്ണതയിലേക്ക് ഞങ്ങളെ നയിക്കുന്നു.

അവലംബം