[LeetCode]--Maximum Product Subarry

タイトル

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array  [2,3,-2,4] ,the contiguous subarray  [2,3]  has the largest product =  6 .

ぶんせき

この問題は、連続するサブシーケンスを探して、その積を最大にすることを意味します.これは比較的典型的な動的計画問題であり、配列ヘッダと末尾からそれぞれインデックスを設定し、resultを最終最大積とし、frontを配列ヘッダからのサブシーケンス最大積とし、endを配列末尾からの最大積とし、result、front、endのたびに最大値を選択してresultに割り当て、一度遍歴すればターゲットサブシーケンスの最大積を得ることができる.
ただし、frontとendの値は0である可能性があるため、1に再割り当てする必要があります.

に答える

class Solution {
public:
    int maxProduct(vector& nums) {
        int length=nums.size();
        int front=1;
        int end=1;
        int result=INT_MIN;
        for(int i=0;i

明らかに、アルゴリズムの複雑さはO(n)であり、ここでnは配列長である.