Menghitung jumlah penjumlahan dari sub-array yang berdekatan dari suatu array

Kita diberi array dengan semua a [ i ] > 0 .$a[1 \ldots n]$$a[i]>0$

Sekarang kita perlu menemukan berapa banyak jumlah yang berbeda dapat dibentuk dari subarrays nya (di mana subarray adalah berbagai bersebelahan dari array, yaitu, untuk beberapa j , k , jumlahnya adalah jumlah dari semua elemen dari subarray). Misalnya, jika a = [ 1 , 2 , 1 ] , maka jawabannya adalah 4: kita dapat membentuk 1 , 2 , 3 , 4 .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Saya tahu bagaimana cara menghitung jumlah jumlah yang berbeda dalam waktu .$O(n^2)$

Selain itu, saya menyadari bahwa ini mirip dengan masalah klasik di mana kita perlu menemukan jumlah substring yang berbeda dari sebuah string. Saya sedang memikirkan kemungkinan membangun susunan sufiks dan menyelesaikannya dengan cara yang serupa (dalam waktu ). Tetapi saya belum dapat menemukan cara untuk memodifikasinya agar berfungsi di sini. Sebagai contoh, jika kita menggunakan array suffix untuk a = [ 1 , 2 , 1 ] kita akan mendapatkan 5 case daripada empat yang dapat diterima. Apakah ini mungkin dilakukan dengan menggunakan array sufiks atau saya berpikir ke arah yang salah?$O(n)$$a=[1,2,1]$

Juga ada satu arah lagi yang saya pikirkan. Membagi dan menaklukkan. Seperti jika saya membagi array menjadi dua bagian setiap kali sampai dikurangi menjadi satu elemen. Satu elemen dapat memiliki satu jumlah. Sekarang jika kita menggabungkan dua elemen tunggal, itu dapat dilakukan dengan dua cara: jika kedua rentang tunggal memiliki elemen yang sama maka kita mendapatkan 2 jumlah yang berbeda, atau jika keduanya memiliki elemen yang berbeda kita mendapatkan 3 jumlah yang berbeda. Tetapi saya tidak dapat menggeneralisasi ini untuk menggabungkan array dengan panjang lebih besar dari 1. Apakah mungkin untuk menggabungkan dua array ukuran m dan mendapatkan jawabannya dalam ?$O(m)$

$O(n^2)$$\Theta(n^2)$

$[1,2,4,8,\dotsc, 2^n]$$\frac{n(n+1)}2$

"Hampir pasti" disebabkan oleh kenyataan bahwa masalahnya tidak memerlukan nilai jumlah sebagai output. Namun, saya tidak berpikir duplikat dapat dihindari tanpa menentukan setidaknya sebagian besar nilai.