数组动归题解 | #连续子数组的最大乘积#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    int max_n = arr[0];
    int GMax=arr[0],GMin=arr[0];


    for(int i=1;i<n;i++){

        int mx = GMax, mn = GMin;
        GMax = max(mx * arr[i] , max(mn*arr[i] , arr[i]));
        GMin = min(mn * arr[i] , min(mx*arr[i] , arr[i]));
        max_n = max(GMax , max_n);
        
    }   
    cout << max_n;
}
// 64 位输出请用 printf("%lld")

涉及数组的+-*/都可以用

dp[i]代表第i个数字为末尾的求解值

然后每轮记得保存下最值