Subarray ສູງສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco ເຟສບຸກ Goldman Sachs ກູໂກ JP Morgan JPMorgan LinkedIn Microsoft Oracle PayPal Paytm Uber
Array ແບ່ງແລະເອົາຊະນະ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ໃນບັນຫາ Subarray ສູງສຸດທີ່ພວກເຮົາໄດ້ໃຫ້ integer array ຕົວເລກ, ຊອກຫາຍ່ອຍທີ່ຕິດກັນ array ເຊິ່ງມີຍອດລວມທີ່ໃຫຍ່ທີ່ສຸດແລະພິມມູນຄ່າ subarray ລວມຍອດສູງສຸດ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ
nums [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
ຜົນຜະລິດ
6

Subarray ສູງສຸດ

ລະບົບວິເຄາະ

ເປົ້າ ໝາຍ ແມ່ນເພື່ອຊອກຫາ ລວມສູງສຸດ ໃນເສັ້ນ (ແຖວຍ່ອຍທີ່ຕິດຕໍ່ກັນ) ໃນແຖວຕົວເລກ, ເຊິ່ງບັນລຸໄດ້ໂດຍໃຊ້ ສູດການຄິດໄລ່ຂອງ Kadane.
ພວກເຮົາໃຊ້ສອງຕົວແປທົ່ວໂລກ, max ແລະ maxTillNow, ບ່ອນທີ່ max ເກັບ ຄຳ ຕອບສຸດທ້າຍ, ແລະ maxTillNow ເກັບຜົນໄດ້ຮັບສູງສຸດຈົນກ່ວາດັດຊະນີ ith.
ເລີ່ມຕົ້ນສູງສຸດທີ່ເຄຍແລະ maxTillNow ເປັນຕົວເລກ [0], ດຳ ເນີນວົງຈາກ 1 ເຖິງ n, ໃນລະຫວ່າງແຕ່ລະ max itill max ຈະກາຍເປັນຕົວເລກສູງສຸດຂອງ [i] ແລະ (maxTillNow + nums [i]) ແລະສູງສຸດຈະກາຍເປັນສູງສຸດຂອງ max ແລະ maxTillNow.
ສຸດທ້າຍ, ພວກເຮົາກັບຄືນສູງສຸດທີ່ເຄຍ, ເຊິ່ງເກັບຮັກສາຍອດ subarray ສູງສຸດ.

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ = O (n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງປະຈຸບັນເລກຢູ່ໃນແຖວທີ່ ກຳ ນົດໃຫ້.
ຄວາມສັບສົນໃນອະວະກາດ = O (1)

ຄໍາອະທິບາຍສໍາລັບ Subarray ສູງສຸດ

ພິຈາລະນາກໍລະນີທີ່ຕົວເລກ = {2, -1, 3, 5, -2, 1}
ເລີ່ມຕົ້ນ,

  • max = nums [0] = 2 ແລະ maxTillNow = 2
  • ສຳ ລັບ i = 1, ຕົວເລກ [i] = -1
    maxTillNow = ສູງສຸດ (-1, -1 + 2) = ສູງສຸດ (-1, 1) = 1
    max = ສູງສຸດ (2, 1) = 2
  • ສຳ ລັບ i = 2, ຕົວເລກ [i] = 3 ສຳ ລັບ i = 4, ຕົວເລກ [i] = -2
  • maxTillNow = ສູງສຸດ (-2, -2 + 9) = ສູງສຸດ (-2, 7) = 7
    max = ສູງສຸດ (9, 7) = 9
  • ສຳ ລັບ i = 5, nums [i] = 1
    maxTillNow = ສູງສຸດ (1, 1 + 7) = ສູງສຸດ (1, 8) = 8
    max = ສູງສຸດ (9, 8) = 9
  • Loop ສິ້ນສຸດລົງແລະພວກເຮົາສົ່ງຄືນສູງສຸດເປັນ 9, ເຊິ່ງແມ່ນຄໍາຕອບ. ນີ້ແມ່ນ 9 ແມ່ນລວມຍອດ subarray ສູງສຸດຂອງພວກເຮົາ.

ລະຫັດ Pseudo

  1. ສຸມໃສ່ສູງສຸດທີ່ເຄຍແລະ maxTillNow ເປັນຕົວເລກ [0]
  2. loop ສຳ ລັບ (i = 1 ເຖິງ ໜ້ອຍ ກວ່າ n)
  3. maxTillNow = ສູງສຸດ (maxTillNow + ຕົວເລກ [i], ຕົວເລກ [i])
  4. ສູງສຸດ = ສູງສຸດ (ສູງສຸດ, maxTillNow)
  5. ສິ້ນສຸດ ສຳ ລັບ
  6. ກັບຄືນສູງສຸດທີ່ເຄຍ

ລະຫັດ JAVA ສຳ ລັບ Subarray ສູງສຸດ

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 ++ ສຳ ລັບ Subarray ສູງສຸດ

#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

ເອກະສານ