Masalah Subarray Maksimum di Java

1. Ikhtisar

Masalah subarray maksimum adalah tugas untuk menemukan rangkaian elemen yang berdekatan dengan jumlah maksimum dalam larik yang diberikan.

Misalnya, dalam larik di bawah ini, sub larik yang disorot memiliki jumlah maksimum (6):

Dalam tutorial ini, kita akan melihat dua solusi untuk menemukan subarray maksimum dalam sebuah array . Salah satunya akan kita desain dengan O (n) waktu dan kompleksitas ruang.

2. Algoritma Brute Force

Brute force adalah pendekatan berulang untuk memecahkan masalah. Dalam banyak kasus, solusinya memerlukan sejumlah iterasi pada struktur data. Di beberapa bagian berikutnya, kami akan menerapkan pendekatan ini untuk menyelesaikan masalah subarray maksimum.

2.1. Pendekatan

Secara umum, solusi pertama yang terlintas dalam pikiran adalah menghitung jumlah setiap subarray yang mungkin dan mengembalikan satu dengan jumlah maksimum.

Untuk memulainya, kita akan menghitung jumlah setiap subarray yang dimulai pada indeks 0. Dan demikian pula, kita akan menemukan semua subarray yang dimulai pada setiap indeks dari 0 hingga n-1 di mana n adalah panjang dari array:

Jadi kita akan mulai dari indeks 0 dan menambahkan setiap elemen ke jumlah berjalan dalam iterasi. Kami juga akan melacak jumlah maksimum yang terlihat sejauh ini . Iterasi ini ditampilkan di sisi kiri gambar di atas.

Di sisi kanan gambar, kita bisa melihat iterasi yang dimulai pada indeks 3 . Di bagian terakhir gambar ini, kita mendapatkan subarray dengan jumlah maksimum antara indeks 3 dan 6 .

Namun, algoritme kami akan terus menemukan semua subarray mulai dari indeks antara 0 dan n-1 .

2.2. Penerapan

Sekarang mari kita lihat bagaimana kita dapat mengimplementasikan solusi ini di Java:

public int maxSubArray(int[] nums) { int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left < n; left++) { int runningWindowSum = 0; for (int right = left; right  maximumSubArraySum) { maximumSubArraySum = runningWindowSum; start = left; end = right; } } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maximumSubArraySum; }

Seperti yang diharapkan, kami memperbarui maximumSubArraySum jika jumlah saat ini lebih dari jumlah maksimum sebelumnya. Khususnya, kami juga memperbarui awal dan akhir untuk mengetahui lokasi indeks subarray ini .

2.3. Kompleksitas

Secara umum solusi brute force melakukan iterasi pada array berkali-kali untuk mendapatkan setiap solusi yang mungkin. Ini berarti waktu yang dibutuhkan oleh solusi ini bertambah secara kuadrat dengan jumlah elemen dalam larik. Ini mungkin bukan masalah untuk array berukuran kecil. Tetapi seiring bertambahnya ukuran array, solusi ini tidak efisien.

Dengan memeriksa kode tersebut, kita juga dapat melihat bahwa ada dua bersarang untuk loop. Oleh karena itu, dapat disimpulkan bahwa kompleksitas waktu dari algoritma ini adalah O (n2) .

Di bagian selanjutnya, kita akan menyelesaikan masalah ini dalam kompleksitas O (n) menggunakan pemrograman dinamis.

3. Pemrograman Dinamis

Pemrograman dinamis memecahkan masalah dengan membaginya menjadi beberapa subproblem yang lebih kecil. Ini sangat mirip dengan teknik pemecahan algoritma divide-and-conquer. Perbedaan utama, bagaimanapun, adalah bahwa pemrograman dinamis memecahkan submasalah hanya sekali.

Kemudian menyimpan hasil dari submasalah ini dan kemudian menggunakan kembali hasil ini untuk menyelesaikan submasalah terkait lainnya. Proses ini dikenal sebagai memoization .

3.1. Algoritma Kadane

Algoritma Kadane adalah solusi populer untuk masalah subarray maksimum dan solusi ini didasarkan pada pemrograman dinamis.

Tantangan terpenting dalam memecahkan masalah pemrograman dinamis adalah menemukan subproblem yang optimal .

3.2. Pendekatan

Mari kita pahami masalah ini dengan cara yang berbeda:

In the image above, we assume that the maximum subarray ends at the last index location. Therefore, the maximum sum of subarray will be:

maximumSubArraySum = max_so_far + arr[n-1]

max_so_far is the maximum sum of a subarray that ends at index n-2. This is also shown in the image above.

Now, we can apply this assumption to any index in the array. For example, the maximum subarray sum that ends at n-2 can be calculated as:

maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]

Therefore, we can conclude that:

maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]

Now, since every element in the array is a special subarray of size one, we also need to check if an element is greater than the maximum sum itself:

maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])

By looking at these equations, we can see that we need to find the maximum subarray sum at every index of the array. Thus, we divided our problem into n subproblems. We can find the maximum sum at every index by iterating the array only once:

The highlighted element shows the current element in the iteration. At every index, we'll apply the equation derived earlier to calculate a value for max_ending_here. This helps us in identifying whether we should include the current element in the subarray or start a new subarray starting at this index.

Another variable, max_so_far is used to store the maximum subarray sum found during the iteration. Once we iterate over the last index, max_so_far will store the sum of the maximum subarray.

3.3. Implementation

Again, let's see how we can now implement the Kadane algorithm in Java, following the above approach:

public int maxSubArraySum(int[] arr) {       int size = arr.length;     int start = 0;     int end = 0;       int maxSoFar = 0, maxEndingHere = 0;       for (int i = 0; i  maxEndingHere + arr[i]) {             start = i;             maxEndingHere = arr[i];         } else             maxEndingHere = maxEndingHere + arr[i];           if (maxSoFar < maxEndingHere) {             maxSoFar = maxEndingHere;             end = i;         }     } logger.info("Found Maximum Subarray between {} and {}", start, end);     return maxSoFar; }

Here, we updated the start and end to find the maximum subarray indices.

3.4. Complexity

Since we only need to iterate the array once, the time complexity of this algorithm is O(n).

So as we can see, the time taken by this solution grows linearly with the number of elements in the array. Consequently, it is more efficient than the brute force approach we discussed in the last section.

4. Conclusion

Dalam tutorial singkat ini, kami telah menjelaskan dua cara untuk menyelesaikan masalah subarray maksimum.

Pertama, kami menjelajahi pendekatan brute force dan melihat bahwa solusi iteratif ini menghasilkan waktu kuadrat. Kemudian, kami membahas algoritma Kadane dan menggunakan pemrograman dinamis untuk menyelesaikan masalah dalam waktu linier.

Seperti biasa, kode sumber lengkap artikel tersedia di GitHub.