Pertanyaan Temukan urutan berdekatan dengan produk terbesar dalam larik bilangan bulat


Saya telah datang dengan kode di bawah tetapi itu tidak memenuhi semua kasus, misalnya:

  1. Larik berisi semua 0

  2. Larik memiliki nilai negatif (agak sulit karena ini tentang menemukan produk sebagai dua int negatif memberi nilai positif)

    public static int LargestProduct(int[] arr)
    {   
        //returning arr[0] if it has only one element
        if (arr.Length == 1) return arr[0];
    
        int product = 1;
        int maxProduct = Int32.MinValue;
    
        for (int i = 0; i < arr.Length; i++)
        {
            //this block store the largest product so far when it finds 0 
            if (arr[i] == 0)
            {
                if (maxProduct < product)
                {
                    maxProduct = product;
                }
                product = 1;
            }
            else 
            {
                product *= arr[i];
            }
        }
        if (maxProduct > product)
            return maxProduct;
        else
            return product;
    }
    

Bagaimana saya bisa memasukkan kasus-kasus di atas / memperbaiki kode. Tolong sarankan.


5
2018-05-12 06:08


asal


Jawaban:


Masalah dasar Anda adalah 2 bagian. Pecahkan dan selesaikan itu menjadi lebih mudah.

1) Temukan semua himpunan bagian yang berdekatan. 

Karena urutan sumber Anda dapat memiliki nilai negatif, Anda tidak semuanya yang dilengkapi untuk membuat penilaian nilai apa pun sampai Anda menemukan setiap bagian, karena negatif nantinya dapat "dibatalkan" oleh yang lain. Jadi biarkan fase pertama hanya menemukan subset.

Contoh bagaimana Anda dapat melakukan ini adalah kode berikut

// will contain all contiguous subsets 
var sequences = new List<Tuple<bool, List<int>>>();

// build subsets 
foreach (int item in source)
{
    var deadCopies = new List<Tuple<bool, List<int>>>();

    foreach (var record in sequences.Where(r => r.Item1 && !r.Item2.Contains(0)))
    {
        // make a copy that is "dead"
        var deadCopy = new Tuple<bool, List<int>>(false, record.Item2.ToList());
        deadCopies.Add(deadCopy);

        record.Item2.Add(item);
    }

    sequences.Add(new Tuple<bool, List<int>>(true, new List<int> { item }));
    sequences.AddRange(deadCopies);
}

Dalam kode di atas, saya membangun semua himpunan bagian yang bersebelahan, sementara mengambil kebebasan tidak menambahkan apa pun ke subset tertentu yang sudah memiliki nilai 0. Anda dapat menghilangkan perilaku tertentu itu jika Anda menginginkannya.

2) Hitung masing-masing produk subset dan bandingkan dengan nilai maks.

Setelah Anda menemukan semua himpunan kualifikasi Anda, bagian selanjutnya mudah.

// find subset with highest product 
int maxProduct = int.MinValue;
IEnumerable<int> maxSequence = Enumerable.Empty<int>();

foreach (var record in sequences)
{
    int product = record.Item2.Aggregate((a, b) => a * b);
    if (product > maxProduct)
    {
        maxProduct = product;
        maxSequence = record.Item2;
    }
}

Tambahkan logika apa pun yang Anda inginkan untuk membatasi panjang sumber asli atau kandidat subset atau nilai produk. Misalnya, jika Anda ingin menerapkan persyaratan panjang minimum pada keduanya, atau jika produk subset dari 0 diperbolehkan jika produk bukan nol tersedia.

Juga, saya tidak mengklaim apa-apa tentang kinerja kode, itu hanya untuk menggambarkan memecah masalah ke dalam bagian-bagiannya.


1
2018-05-12 18:20



Saya mendasarkan jawaban saya pada asumsi bahwa jika Anda memiliki lebih dari 1 elemen dalam array, Anda ingin mengalikan setidaknya 2 bilangan bulat berdekatan untuk memeriksa output, yaitu dalam larik {-1, 15}, output yang Anda inginkan adalah -15 dan bukan 15).

Masalah yang perlu kita pecahkan adalah melihat semua kombinasi perkalian yang mungkin dan menemukan produk maksimal dari mereka.

Jumlah total produk dalam susunan n bilangan bulat adalah nC2 yaitu jika ada 2 elemen, maka kombinasi perkalian total akan menjadi 1, untuk 3, akan menjadi 3, untuk 4, akan menjadi 6 dan seterusnya.

Untuk setiap angka yang kita miliki dalam array yang masuk, itu harus dikalikan dengan semua perkalian yang kita lakukan dengan elemen terakhir dan menyimpan produk maksimal hingga sekarang dan jika kita melakukannya untuk semua elemen, pada akhirnya kita akan ditinggalkan. dengan produk maksimal.

Ini seharusnya bekerja untuk negatif dan nol.

    public static long LargestProduct(int[] arr)
    {
        if (arr.Length == 1)
            return arr[0];

        int lastNumber = 1;
        List<long> latestProducts = new List<long>();
        long maxProduct = Int64.MinValue;
        for (int i = 0; i < arr.Length; i++)
        {
            var item = arr[i];
            var latest = lastNumber * item;
            var temp = new long[latestProducts.Count];
            latestProducts.CopyTo(temp);
            latestProducts.Clear();
            foreach (var p in temp)
            {
                var product = p * item;
                if (product > maxProduct)
                    maxProduct = product;
                latestProducts.Add(product);
            }
            if (i != 0)
            {
                if (latest > maxProduct)
                    maxProduct = latest;
                latestProducts.Add(latest);
            }
            lastNumber = item;
        }
        return maxProduct;
    }

Jika Anda ingin produk maksimum juga memasukkan elemen tunggal yang ada dalam larik yaitu {-1, 15} harus ditulis 15, maka Anda dapat membandingkan produk maks dengan elemen larik yang diproses dan yang seharusnya memberi Anda produk maksimal jika elemen tunggal adalah angka maks. Ini dapat dicapai dengan menambahkan kode berikut di dalam for for loop di bagian akhir.

if (item > maxProduct)
    maxProduct = item;

2
2017-08-10 06:58



Saya pikir Anda harus memiliki 2 produk pada saat yang sama - mereka akan berbeda dalam tanda-tanda. Tentang kasus, ketika semua nilai nol - Anda dapat memeriksa di akhir jika maxProduct masih Int32.MinValue (jika Int32.MinValue benar-benar tidak mungkin) Varian saya:

int maxProduct = Int32.MinValue;
int? productWithPositiveStart = null;
int? productWithNegativeStart = null;

for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == 0)
        {
            productWithPositiveStart = null;
            productWithNegativeStart = null;
        } 
        else 
        {
            if (arr[i] > 0 && productWithPositiveStart == null) 
            {
                 productWithPositiveStart = arr[i];            
            }
            else if (productWithPositiveStart != null)
            {
                 productWithPositiveStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithPositiveStart);
            }
            if (arr[i] < 0 && productWithNegativeStart == null)
            {
                 productWithNegativeStart = arr[i];
            }
            else if (productWithNegativeStart != null) 
            {
                 productWithNegativeStart *= arr[i];
                 maxProduct = Math.max(maxProduct, productWithNegativeStart);
            }
            maxProduct = Math.max(arr[i], maxProduct);
        }            
    }
 if (maxProduct == Int32.MinValue) 
 {
     maxProduct = 0;
 }

0
2018-05-12 06:31



Pada tingkat tinggi, algoritma Anda saat ini membagi array pada 0 dan mengembalikan produk bersebelahan terbesar dari sub-array ini. Setiap iterasi lebih lanjut akan berada pada proses pencarian produk bersebelahan terbesar dari sub-array di mana tidak ada elemen yang 0.

Untuk memperhitungkan angka negatif, kita jelas harus terlebih dahulu menguji apakah produk dari salah satu dari sub-array ini negatif, dan mengambil beberapa tindakan khusus jika itu.

Hasil negatif berasal dari jumlah nilai negatif ganjil, jadi kita perlu menghapus salah satu dari nilai negatif ini untuk membuat hasilnya positif lagi. Untuk melakukan ini, kami menghapus semua elemen hingga angka negatif pertama, atau angka negatif terakhir dan semua elemen setelah itu, mana yang menghasilkan produk tertinggi.

Untuk memperhitungkan suatu array dari semua 0, cukup gunakan 0 sebagai awal maxProduct Anda. Jika array adalah nilai negatif tunggal, Anda menangani kasus khusus dari satu elemen berarti yang dikembalikan. Setelah itu, akan selalu ada produk sub-urutan positif, atau seluruh susunan adalah 0 dan seharusnya kembali 0.


0
2018-05-12 17:53



itu bisa dilakukan di O(N). ini didasarkan pada ide sederhana: hitung minimumnya (minCurrent) dan maksimum (maxCurrent) sampai i. Ini dapat dengan mudah diubah agar sesuai dengan kondisi seperti: {0,0,-2,0} or {-2,-3, -8} or {0,0}

a[] = {6, -3, 2, 0, 3, -2, -4, -2, 4, 5}

steps of the algorithm given below for the above array a :

private static int getMaxProduct(int[] a) {
    if (a.length == 0) {
        throw new IllegalArgumentException();
    }
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE;
    for (int current : a) {
        if (current > 0) {
            maxCurrent = maxCurrent * current;
            minCurrent = Math.min(minCurrent * current, 1);
        } else if (current == 0) {
            maxCurrent = 1;
            minCurrent = 1;
        } else {
            int x = maxCurrent;
            maxCurrent = Math.max(minCurrent * current, 1);
            minCurrent = x * current;
        }
        if (max < maxCurrent) {
            max = maxCurrent;
        }
    }
    //System.out.println(minCurrent);
    return max;
}

0
2017-10-04 19:40