問題

給定一個double類型的數組arr, 其中的元素可正, 可負, 可0, 返回子數組累乘的最大乘積.

例如, arr = [-2.5, 4, 0, 3, 0.5, 8, -1], 子數組{3, 0.5, 8}累乘可以獲得最大的乘積12, 所以返回12.

分析

最大累乘積, 就是在以每個元素arr[i], 0=<i<= size-1 為結尾的子數組的最大累乘積中, 最大的值.
以arr[i]為結尾的累乘積由三種情況, 從這三種情況中選擇最大的作為當前最大累乘積:

  1. curMax * arr[i], curMax為以arr[i-1]為結尾的最大累乘積. 如數組[1, 2, 3, 4], 當i = 3時, curMax = 1 * 2 * 3 = 6. curMax * arr[3] = 24
  2. curMin * arr[i], curMin為以arr[i-1]為結尾的最小累乘積, 考慮到的情況是curMin為負數, 並且arr[i]也為負數的場景. 如數組[1,2,-3,-4], 當i = 3時, curMin = 1 * 2 * -3 = -6, curMin * arr[i] = -6 * -4 = 24
  3. arr[i], 最大累乘積是arr[i]自身, 如數組[1, 2, -3], 以-3結尾的最大累乘積為 -3
class Solution
{
public:
    double maxMulti(std::vector<double>& nums)
    {   
        if (nums.size() == 0)
        {   
            return 0;
        }   
        double curMax = nums[0];
        double curMin = nums[0];
        double result = nums[0];
        for (std::vector<double>::iterator cur = nums.begin() + 1; cur < nums.end(); ++cur)
        {   
            double cand1 = curMax * *cur;
            double cand2 = curMin * *cur;
            double cand3 = *cur;
            curMax = std::max(cand1, std::max(cand2, cand3));
            curMin = std::min(cand1, std::min(cand2, cand3));
            result = std::max(curMax, result);
        }   
        return result;
    }   
};

int main()
{
    Solution solution;
    std::vector<double> nums = {-2.5, 4, 0, 3, 0.5, 8, -1};
    std::cout << solution.maxMulti(nums) << std::endl;
}
分享