ຜົນລວມສູງສຸດຂອງອົງປະກອບທີ່ບໍ່ສາມາດຕັດຕໍ່ໄດ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Amazon American Express ເຟສບຸກ ກູໂກ Grab ກະເປົາເງິນ Oxigen ຫ້ອງ OYO Paytm SnapChat Walmart Labs Yahoo
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ໃນ“ ຜົນລວມສູງສຸດຂອງອົງປະກອບທີ່ບໍ່ຕັດຕໍ່” ໃຫ້ 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. ສຸດທ້າຍ, ຫຼັງຈາກ ຄຳ ຕອບແບບ traversal ຈະສູງສຸດຂອງ 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.

ການປະຕິບັດ

ໂປຣແກຣມ 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 Program ສຳ ລັບການຊອກຫາລວມຍອດສູງສຸດຂອງອົງປະກອບທີ່ບໍ່ສາມາດຕັດຕໍ່ໄດ້

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) ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ຕົວແປບາງຢ່າງເທົ່ານັ້ນທີ່ເຮັດໃຫ້ພວກເຮົາມີຄວາມສັບສົນໃນພື້ນທີ່ຄົງທີ່.

ເອກະສານ