Maksimum subarray

Maksimum Subarray problemində bir tam array nums, bitişik alt tapın array ən böyük cəmi olan və maksimum cəmi subarray dəyərini yazdıran.

misal

Input
saylar [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Buraxılış
6

Pin

Alqoritm

Məqsəd tapmaqdır maksimum cəmi istifadə edərək əldə edilən bir sıra (bitişik alt sıra) ədədlər sırasındadır Kadane Alqoritmi.
Max və maxTillNow iki qlobal dəyişəndən istifadə edirik, burada max son cavabı və maxTillNow maksimum nəticəni indeksə qədər saxlayır.
Max və maxTillNow'u nums [0] olaraq başladın, hər bir təkrarlama zamanı maxTillNow maksimum nums [i] və (maxTillNow + nums [i]) olur və max maksimum və maxTillNow olur.
Nəhayət, maksimum subarray cəmini saxlayan maks.

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n) burada n - verilən massivdə mövcud olan tam ədədin sayı.
Kosmik Mürəkkəblik = O (1)

Maksimum Subarray üçün izah

Nums = {2, -1, 3, 5, -2, 1} olduğu vəziyyəti nəzərdən keçirin
Başlat,

• max = nums [0] = 2 və maxTillNow = 2
• i = 1 üçün nums [i] = -1
  maxTillNow = max (-1, -1 + 2) = max (-1, 1) = 1
  max = max (2, 1) = 2
• i = 2 üçün nums [i] = 3 i = 4 üçün, nums [i] = -2
• maxTillNow = max (-2, -2 + 9) = max (-2, 7) = 7
  max = max (9, 7) = 9
• i = 5 üçün nums [i] = 1
  maxTillNow = max (1, 1 + 7) = max (1, 8) = 8
  max = max (9, 8) = 9
• Döngə bitir və maksimum 9 kimi qaytarırıq, bu da cavabdır. Budur 9 maksimum subarray cəmimizdir.

Saxta Kod

1. Max və maxTillNow ədədi kimi rəqəmləşdirin [0]
2. üçün loop (i = 1-dən n-dən az)
3. maxTillNow = maksimum (maxTillNow + nums [i], nums [i])
4. max = maksimum (max, maxTillNow)
5. üçün son
6. maksimum qayıt

Maksimum Subarray üçün JAVA Kodu

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

Maksimum subarray üçün C ++ kodu

#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

References