Максималды ішкі массив


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Cisco Facebook Голдман Сакс Google JP Morgan JPMorgan LinkedIn Microsoft Oracle PayPal Paytm қиятын
Array Бөліңіз және жеңіңіз Динамикалық бағдарламалау

Subarray максималды мәселесінде біз бүтін сан массив нөмірлері, сабақтас бағыныңқылықты табыңыз массив ең үлкен қосындысы бар және максималды қосынды ішкі мәнін басатын.

мысал

енгізу
сандар [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
шығыс
6

Максималды ішкі массив

Алгоритм

Мақсат - іздеу максималды сома жолында (сабақтас кіші жиым), оны қолдану арқылы қол жеткізілетін nums массивінде Каданенің алгоритмі.
Біз max және maxTillNow екі жаһандық айнымалыларды қолданамыз, мұнда max соңғы жауапты сақтайды, және maxTillNow максималды нәтижені ith индексіне дейін сақтайды.
Max және maxTillNow-ті nums [0] ретінде инициализациялаңыз, циклды 1-ден n-ге дейін жүргізіңіз, maxTillNow әрбір итерация кезінде nums [i] және (maxTillNow + nums [i]) максимумға айналады, ал max максимум max және maxTillNow болады.
Соңында, максималды субарра сомасын сақтайтын максималды мәнді қайтарамыз.

Күрделілікті талдау

Уақыттың күрделілігі = O (N) Мұндағы n - берілген жиымдағы бүтін санның саны.
Ғарыштың күрделілігі = O (1)

Максималды ішкі массив туралы түсініктеме

Nums = {2, -1, 3, 5, -2, 1} болатын жағдайды қарастырайық
Инициализациялау,

  • max = nums [0] = 2 және maxTillNow = 2
  • i = 1 үшін nums [i] = -1
    maxTillNow = max (-1, -1 + 2) = max (-1, 1) = 1
    max = max (2, 1) = 2
  • i = 2 үшін nums [i] = 3 i = 4 үшін, nums [i] = -2
  • maxTillNow = max (-2, -2 + 9) = max (-2, 7) = 7
    max = max (9, 7) = 9
  • i = 5 үшін nums [i] = 1
    maxTillNow = max (1, 1 + 7) = max (1, 8) = 8
    max = max (9, 8) = 9
  • Ілмек аяқталады және біз максимумды 9 деп қайтарамыз, бұл жауап. Міне, 9 - бұл максималды қосынды сомасы.

Псевдо коды

  1. Max және maxTillNow сандарын интрализациялау [0]
  2. үшін цикл (i = 1 -ден n-ге дейін)
  3. maxTillNow = максимум (maxTillNow + nums [i], nums [i])
  4. max = максимум (max, maxTillNow)
  5. үшін аяқтау
  6. қайтару макс

Максималды ішкі массивке арналған JAVA коды

public class MaximumSubarray {
    public static void main(String[] args) {
        // Input array
        int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        
        // Find the maximum subarray using Kadane's algorithm
        int maxSum = findMaxSubarray(nums);
        
        // Print the answer
        System.out.println(maxSum);
    }
    
    private static int findMaxSubarray(int[] nums) {
        // Initialise max and maxTillNow as nums[0]
        int max = nums[0];
        int maxTillNow = nums[0];
        
        // Loop through the array
        for (int i = 1; i < nums.length; i++) {
            // maxTillNow is max of curr element or maxTillNow + curr element
            maxTillNow = Math.max(nums[i], maxTillNow + nums[i]);
            // max is maximum of max and maxTillNow
            max = Math.max(max, maxTillNow);
        }
        
        // Return the result
        return max;
    }
}

Максималды ішкі массивке арналған C ++ коды

#include <bits/stdc++.h>
using namespace std;

int findMaxSubarray(int *nums, int n) {
    // Initialise max and maxTillNow as nums[0]
    int max = nums[0];
    int maxTillNow = nums[0];
    
    // Loop through the array
    for (int i = 1; i < n; i++) {
        // maxTillNow is max of curr element or maxTillNow + curr element
        maxTillNow = std::max(nums[i], maxTillNow + nums[i]);
        // max is maximum of max and maxTillNow
        max = std::max(max, maxTillNow);
    }
    
    // Return the result
    return max;
}

int main() {
    // Input array
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    int n = sizeof(nums) / sizeof(*nums);
    
    // Find the maximum subarray using Kadane's algorithm
    int maxSum = findMaxSubarray(nums, n);

    // Print the answer
    cout<<maxSum<<endl;
    
    return 0;
}
{-2, 1, -3, 4, -1, 2, 1, -5, 4}
6

Әдебиеттер тізімі