비 연속 요소의 최대 합계

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

주어진 "비 연속 요소의 최대 합계"에서 정렬, 비 연속 요소의 최대 합을 찾아야합니다. 바로 이웃 번호를 추가 할 수 없습니다. 예를 들어 [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을 XNUMX이되도록 초기화합니다.
4. 각 요소에 대해 최대 incl_sum 및 excl_sum을 찾으십시오.
5. incl_sum은 현재 요소보다 인덱스가 하나 적을 때까지 excl_sum이 계산되었으므로 현재 요소와 excl_sum의 합과 같습니다.
6. excl_sum은 4 단계에서 찾은 최대 값입니다.
7. 마지막으로 순회 후 응답은 최대 incl_sum 및 excl_sum이됩니다.

연속되지 않는 요소의 최대 합계를 찾기위한 설명

입력

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

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
마지막으로 대답은 max (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;
}

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