一千萬個為什麽

搜索

在整數數組中查找具有最大乘積的連續序列

我已經提出了下面的代碼但是並不滿足所有情況,例如:

  1. Array consisting all 0's

  2. Array having negative values(it's bit tricky since it's about finding product as two negative ints give positive value)

    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;
    }
    

如何合並上述案例/更正代碼。請建議。

最佳答案

我的答案基於這樣的假設:如果你在數組中有超過1個元素,你會想要乘以至少2個連續的整數來檢查輸出,即在{-1,15}的數組中,你的輸出想要是-15而不是15)。

我們需要解決的問題是查看所有可能的乘法組合,並找出它們中的最大乘積。

n個整數數組中的乘積總數為nC2,即如果有2個元素,那麽總乘法組合將是1,對於3,它將是3,對於4,它將是6,依此類推。

對於我們在傳入數組中的每個數字,它必須乘以我們對最後一個元素所做的所有乘法,並保持最大乘積直到現在,如果我們對所有元素進行,最後我們將離開最大的產品。

這應該適用於否定和零。

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

        int lastNumber = 1;
        List latestProducts = new List();
        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;
    }

如果您希望最大產品也包含陣列中存在的單個元素,即{-1,15}應該寫為15,那麽您可以將最大乘積與正在處理的陣列的元素進行比較,並且應該為您提供最大乘積如果單個元素是最大數字。 這可以通過在最後的for循環中添加以下代碼來實現。

if (item > maxProduct)
    maxProduct = item;

轉載註明原文: 在整數數組中查找具有最大乘積的連續序列