leetcode-152-线性DP-乘积最大子数组 发表于 2020-04-16 | 分类于 数据结构与算法 题目 解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758// 动态规划class Solution {public: tuple<int, int> m_min_max(int a, int b, int c){ int m_min = min(a, min(b, c)); int m_max = max(a, max(b, c)); return make_tuple(m_min, m_max); } int maxProduct(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; // dp[i][0], dp[i][1] 表示以第i个元素结尾的子序列的最大子序乘积的最小与最大值 vector<vector<int>> dp(n, vector<int>(2)); dp[0][0] = nums[0]; dp[0][1] = nums[0]; int res = dp[0][1]; for(int i = 1; i < n; ++i){ tie(dp[i][0], dp[i][1]) = m_min_max(dp[i-1][0] * nums[i], dp[i-1][1] * nums[i], nums[i]); if(dp[i][1] > res) res = dp[i][1]; } return res; }};// 动态规划,优化空间复杂度class Solution {public: tuple<int, int> m_min_max(int a, int b, int c){ int m_min = min(a, min(b, c)); int m_max = max(a, max(b, c)); return make_tuple(m_min, m_max); } int maxProduct(vector<int>& nums) { int n = nums.size(); if(n == 0) return 0; if(n == 1) return nums[0]; int i_min = nums[0]; // 保存第i个元素结尾的连续子序列的最小乘积 int i_max = nums[0]; // 保存第i个元素结尾的连续子序列的最大乘积 int res = i_max; for(int i = 1; i < n; ++i){ tie(i_min, i_max) = m_min_max(i_min*nums[i], i_max*nums[i], nums[i]); if(i_max > res) res = i_max; } return res; }};