Kode Program (Python)

# jumlah-subarray.py
# oleh: hy

def jumlah_subarray_1(arr, jum):
   n = len(arr)
   for i in range(n):
       for j in range(i+1, n+1):
           if sum(arr[i:j]) > jum:
               break
           if sum(arr[i:j]) == jum:
               return [i+1, j]
   return [-1]

def jumlah_subarray_2(arr, jum):
   n = len(arr)
   for i in range(n):
       total = arr[i]
       j = i+1
       while j <= n:
           if total == jum:
               return [i+1, j]
           if total > jum or j == n:
               break
           total += arr[j]
           j += 1
   return [-1]

def info(arr, hasil, jum):
   print(', '.join([str(i) for i in hasil]))
   if len(hasil) == 2:
       print(f'=> Jumlah = {jum} ditemukan pada elemen ke-{hasil[0]} sampai elemen ke-{hasil[1]} dari array\n{arr}.')
   else:
       print(f'=> Jumlah = {jum} tidak ditemukan pada array\n{arr}.')
   print()

import random

def main():
   print()

   jum = 12
   arr = [2, 3, 4, 5, 7]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)
   jum = 9
   arr = [1,2,3,4,5,6,7,8,9,10]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

   jum = 40
   arr = [1,2,3,4,5,6,7,8,9,10]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

   jum = 468
   arr = [135,101,170,125,79,159,163,65,106,146,\
       82,28,162,92,196,143,28,37,192,5,103,154,\
       93,183,22,117,119,96,48,127,172,139,70,113,\
       68,100,36,95,104,12,123,134]
   hasil = jumlah_subarray_1(arr, jum)
   info(arr, hasil, jum)
   hasil = jumlah_subarray_2(arr, jum)
   info(arr, hasil, jum)

if __name__ == '__main__':
   main()
______________

Pembahasan

Pada program di atas, diberikan dua fungsi yang melakukan hal yang sama, yaitu menemukan indeks awal dan akhir subarray, yang memiliki jumlah elemen sama dengan kriteria yang diinginkan.

Fungsi jumlah_subarray_1(arr, jum)mengandalkan fungsi built-insum() pada Python. Sedangkan fungsi jumlah_subarray_2(arr, jum) menggunakan cara "manual".

Karena dalam fungsi sum() secara internal sudah mengandung iterasi, maka pada fungsi jumlah_subarray_1(arr, jum), "level" iterasinya akan bertambah dalam, sehingga jika kita ukur waktu eksekusinya, kemungkinan besar fungsi jumlah_subarray_2(arr, jum) membutuhkan waktu yang lebih singkat, karena penjumlahan nilai elemen dilakukan pada iterasi utama.

Untuk array berukuran kecil, mungkin selisih waktunya sangat kecil. Namun, untuk array dengan ukuran yang besar, pasti selisih waktunya akan bertambah besar.
______________

Contoh Hasil Eksekusi

2, 4
=> Jumlah = 12 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[2, 3, 4, 5, 7].

2, 4
=> Jumlah = 12 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[2, 3, 4, 5, 7].

2, 4
=> Jumlah = 9 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

2, 4
=> Jumlah = 9 ditemukan pada elemen ke-2 sampai elemen ke-4 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

6, 10
=> Jumlah = 40 ditemukan pada elemen ke-6 sampai elemen ke-10 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

6, 10
=> Jumlah = 40 ditemukan pada elemen ke-6 sampai elemen ke-10 dari array
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

38, 42
=> Jumlah = 468 ditemukan pada elemen ke-38 sampai elemen ke-42 dari array
[135, 101, 170, 125, 79, 159, 163, 65, 106, 146, 82, 28, 162, 92, 196, 143, 28, 37, 192, 5, 103, 154, 93, 183, 22, 117, 119, 96, 48, 127, 172, 139, 70, 113, 68, 100, 36, 95, 104, 12, 123, 134].

38, 42
=> Jumlah = 468 ditemukan pada elemen ke-38 sampai elemen ke-42 dari array
[135, 101, 170, 125, 79, 159, 163, 65, 106, 146, 82, 28, 162, 92, 196, 143, 28, 37, 192, 5, 103, 154, 93, 183, 22, 117, 119, 96, 48, 127, 172, 139, 70, 113, 68, 100, 36, 95, 104, 12, 123, 134].