Üst-üstə düşməyən 3 alt cədvəlin maksimum cəmi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Facebook
Geyim Dinamik proqramlaşdırmaBaxılıb 66

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Üst-üstə düşməyən 3 subarrays probleminin maksimum cəmində bir verdik array müsbət tam ədədin sayı, maksimum cəmi olan k uzunluğunun üst-üstə düşməyən üç subarasını tapın və başlanğıc indekslərini qaytarın.

misal

Input:
saylar [] = {1, 2, 1, 2, 6, 7, 5, 1}
k = 2
Çıxış:
{0, 3, 5}

Üst-üstə düşməyən 3 alt cədvəlin maksimum cəmi üçün alqoritm

Fikir bütün uzunluqlu fasiləsiz subrayların cəmini saxlayan bir cəm massivi qurmaqdır. İ indeksi üçün ondan alınan maksimum cəm ​​[i] + indeksdən 0-a (i -k) qədər cəmin maksimum dəyəri + cəmin uzunluğuna qədər (i + k) cəmin maksimum dəyəridir.

Soldan və sağdan daha 2 massiv yaradın, burada sol, indeksə qədər bitişik bir uzunluqlu bir massivin maksimum cəminin indeksini saxlayır və sağ da eyni, lakin sondan başlayaraq saxlayır.

Dizin k-dən indeksə (cəmi uzunluğu - k) qədər olan sıra cəmini keçin, hər bir indeks üçün ondan alınan maksimum cəm cəm [i] + cəm [sol [i - k]] + cəm [sağ [i + k]].
Bütün mümkün cəmlər üçün maksimum cəmi və müvafiq indeksləri tapın.

Üst-üstə düşməyən 3 subarraysın maksimum cəminin izahı

Yuxarıdakı nümunədəki massivi nəzərdən keçirin,
nums [] = {1, 2, 1, 2, 6, 7, 5, 1} və k = 2

Nums array üçün 2 uzunluğunda bitişik alt məcmuların bütün mümkün cəmlərini saxlayan cəmi array.
cəmi [] = {3, 3, 3, 8, 13, 12, 6}

Alqoritmdə təsvir olunduğu kimi sola və sağa massivlər yaradın
sol [] = {0, 0, 0, 3, 4, 4, 4}
sağ [] = {4, 4, 4, 4, 4, 5, 6}

İndeks 2-dən indeks 4-ə qədər başlayan cəmi cərgəsində keçin,

  • i = 2, cəmi [i] = 3
    indeksdən alınan cəm 2 = 3 + (cəmi [sol [2 - 2]]) + (cəmi [sağ [2 + 2]]) = 19
  • i = 3, cəmi [i] = 8
    indeksdən alınan cəm 3 = 8 + (cəmi [sol [3 - 2]]) + (cəmi [sağ [3 + 2]]) = 23
  • i = 4, cəmi [i] = 13
    indeksdən alınan cəm 4 = 13 + (cəmi [sol [4 - 2]]) + (cəmi [sağ [4 + 2]]) = 22

Üst-üstə düşməyən 3 alt cədvəlin maksimum cəmiPin

Alınan maksimum məbləğ = 23 və başlanğıc göstəriciləri {0, 3, 5}

Üst üstə düşməyən 3 subarraysin maksimum cəmi üçün JAVA kodu

public class MaximumSumOfThreeNonOverlappingIntervals {
    private static int[] findInicies(int[] nums, int k) {
        int n = nums.length;

        // build sum array that stores the sum of all k length continuous subarrays
        int sum[] = new int[n - k + 1];
        int currSum = 0;
        for (int i = 0; i < k; i++) {
            currSum += nums[i];
        }

        sum[0] = currSum;

        for (int i = k;i < n; i++) {
            currSum -= nums[i - k];
            currSum += nums[i];
            sum[i - k + 1] = currSum;
        }

        // Create left array that stores the index of maximum sum of contiguous array of length k upto that index
        int left[] = new int[sum.length];
        int best = 0;
        for (int i = 0; i < sum.length; i++) {
            if (sum[i] > sum[best]) {
                best = i;
            }
            left[i] = best;
        }

        best = sum.length - 1;
        // Create right array that stores the index of maximum sum of contiguous array of length k upto that index
        // starting from end
        int right[] = new int[sum.length];
        for (int i = sum.length - 1; i >= 0; i--) {
            if (sum[i] >= sum[best]) {
                best = i;
            }
            right[i] = best;
        }

        // Initialise ans array as -1
        int ans[] = new int[] {-1, -1, -1};
        // Traverse in sum array from index k to (sum length - k)
        for (int i = k; i < sum.length - k; i++) {
            // Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
            int l = left[i - k];
            int r = right[i + k];
            if (ans[0] == -1 ||
                    (sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
                // Update the indices if the max sum is greater than the actual max sum
                ans[0] = l;
                ans[1] = i;
                ans[2] = r;
            }
        }

        // return ans array
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[] {1,2,1,2,6,7,5,1};
        int k = 2;

        int indices[] = findInicies(nums, k);
        for (int i = 0; i < 3; i++)
            System.out.print(indices[i] + " ");
        System.out.println();
    }
}

Üst-üstə düşməyən 3 subarraysin maksimum cəmi üçün C ++ kodu

#include <iostream>
#include <vector>
using namespace std;

void findIndices(int *nums, int k, int n, vector<int> &ans) {
    // build sum array that stores the sum of all k length continuous subarrays
    int sum[n- k + 1];
    int currSum = 0;
    for (int i = 0; i < k; i++) {
        currSum += nums[i];
    }

    sum[0] = currSum;

     for (int i = k;i < n; i++) {
        currSum -= nums[i - k];
        currSum += nums[i];
        sum[i - k + 1] = currSum;
    }
    
    // Create left array that stores the index of maximum sum of contiguous array of length k upto that index
    int left[n - k + 1];
    int best = 0;
    for (int i = 0; i < n - k + 1; i++) {
        if (sum[i] > sum[best]) {
            best = i;
        }
        left[i] = best;
    }
    
    best = n - k;
    // Create right array that stores the index of maximum sum of contiguous array of length k upto that index
    // starting from end
    int right[n - k + 1];
    for (int i = n - k; i >= 0; i--) {
        if (sum[i] >= sum[best]) {
            best = i;
        } 
        right[i] = best;
    }
    
    // Initialise ans array as -1
    ans.push_back(-1);
    ans.push_back(-1);
    ans.push_back(-1);
    // Traverse in sum array from index k to (sum length - k)
    for (int i = k; i < (n - k + 1 - k); i++) {
        // Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
        int l = left[i - k];
        int r = right[i + k];
        if (ans[0] == -1 ||
                (sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
            // Update the indices if the max sum is greater than the actual max sum
            ans[0] = l;
            ans[1] = i;
            ans[2] = r;
        }
    }
}

int main() {
    int nums[] = {1,2,1,2,6,7,5,1};
    int k = 2;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    vector<int> ans;
    findIndices(nums, k, n, ans);
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}
0 3 5

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n)

burada n - verilən massivdə mövcud olan elementlərin sayı.

References

Crack Sistemi Dizayn Müsahibələri
Translate »