leetcode：最大连续数组和乘积

leetcode：最大连续数组和/乘积

思路：
dp，选择之前+现在的 or只选当前的

class Solution {
public:
    int maxSubArray(vector& nums) {
        //以i为结尾的
        vector maxF(nums);
        for(int i = 1; i < nums.size(); i++) {
            maxF[i] = max(maxF[i - 1] + nums[i], nums[i]);
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

maxF(i)表示以第i个结尾

最大乘积：

思路：由于乘积最大可能是之前最大乘现在最大or之前最小乘现在最小
F【i】表示乘积以第i个结尾

class Solution {
public:
    int maxProduct(vector& nums) {
        // 第i个元素结尾的max和min
        vector maxF(nums), minF(nums);
        for(int i = 1; i < nums.size(); i++) {
            // 最大和最小的都要记录
            maxF[i] = max(maxF[i - 1] * nums[i], max(minF[i - 1] * nums[i], nums[i]));
            minF[i] = min(maxF[i - 1] * nums[i], min(minF[i - 1] * nums[i], nums[i]));
        }

        return *max_element(maxF.begin(), maxF.end());


    }
};

总结：
1.复制构造函数的使用
2.最大连续和/乘积，使用dp，f【i】表示以i结尾的局部结果
3.*max_element(v.begin(),v.end())求最大