禅城区建网站公司,广西哪家公司做网站的,嘉兴网站公司哪家好,龙信建设集团网站动态规划#xff0c;注意负负得正#xff0c;dp交换。
题目 注意这里的dp的乘积要求最大#xff0c;而两个很大的负数相乘也是大的#xff0c;因此在每遍历到一个数时要存一个最大值的dp与一个最小值的dp#xff0c;然后遍历完后再去存ans的dp。由于存在负数#xff0c;…动态规划注意负负得正dp交换。
题目 注意这里的dp的乘积要求最大而两个很大的负数相乘也是大的因此在每遍历到一个数时要存一个最大值的dp与一个最小值的dp然后遍历完后再去存ans的dp。由于存在负数那么会导致最大的变最小的最小的变最大的。因此还需要维护当前最小值。
时间复杂度 O(n)空间复杂度 O(1)。
class Solution {public int maxProduct(int[] nums) {int ans Integer.MIN_VALUE, imax 1, imin 1;for(int i0; inums.length; i){if(nums[i] 0){ // 负数交换这样每次循环后imax最大imin最小int tmp imax;imax imin;imin tmp;}imax Math.max(imax*nums[i], nums[i]);//维护大的imin Math.min(imin*nums[i], nums[i]);//维护小的ans Math.max(ans, imax);}return ans;}
}动态规划题还是要多练。
