专栏首页SnailTyan、Maximum Product Subarray

、Maximum Product Subarray

1. 问题描述

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.

2. 求解

这个题跟Leetcode 53——Maximum Subarray类似,可以用三重循环,两种循环解决。但最好的还是用动态规划解决,找出状态转移方程最关键。由于乘积可能为负数,负负得正,因此第i-1次的乘积最大值(maxValuePre)与最小值(minValuePre)都需要保留。当然也可以定义最大值最小值数组来保存第i次乘积的最大值(maxValue)与最小值(minValue)。与Maximum Subarray相比,最大值为maxValue = max(minValuePre * nums[i], maxValuePre * nums[i], nums[i]),最小值同样如此。

没有定义最大值数组与最小值数组

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxValue = nums[0];
        int minValue = nums[0];
        int result = nums[0];
        int maxValuePre = nums[0], minValuePre = nums[0];
        for(int i = 1; i < n; i++) {
            maxValue = Math.max(minValuePre * nums[i], Math.max(maxValuePre * nums[i], nums[i]));
            minValue = Math.min(minValuePre * nums[i], Math.min(maxValuePre * nums[i], nums[i]));
            if(maxValue > result) {
                result = maxValue;
            }
            maxValuePre = maxValue;
            minValuePre = minValue;
        }
        return result;
    }
}

定义最大值数组与最小值数组

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int maxValue[] = new int[nums.length];
        int minValue[] = new int[nums.length];
        maxValue[0] = nums[0];
        minValue[0] = nums[0];
        int result = nums[0];
        for(int i = 1; i < n; i++) {
            maxValue[i] = Math.max(minValue[i - 1] * nums[i], Math.max(maxValue[i - 1] * nums[i], nums[i]));
            minValue[i] = Math.min(minValue[i - 1] * nums[i], Math.min(maxValue[i - 1] * nums[i], nums[i]));
            if(maxValue[i] > result) {
                result = maxValue[i];
            }
        }
        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 532. K-diff Pairs in an Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • Leetcode 41. First Missing Positive

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 189. Rotate Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Golang Leetcode 654. Maximum Binary Tree.go

    递归 先找到最大的,作为root 然后左边的作为Left,右边的作为Right

    anakinsun
  • 【LeetCode】448. Find All Numbers Disappeared in an Array

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 图解冒泡排序

    在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

    CoderJed
  • 46. 全排列【回溯算法】

    输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], ...

    韩旭051
  • 【专知-关关的刷题日记15】Leetcode 27. Remove Element 方法1、2、3

    题目 Given an array and a value, remove all instances of that value in place and r...

    WZEARW
  • 经典八种排序算法总结(带动画演示)

    算法和数据结构是一个程序员的内功,所以经常在一些笔试中都会要求手写一些简单的排序算法,以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法,一起学习一下...

    java技术爱好者
  • [leetcode数组系列]3 删除排序数组中的重复项

    1 leetcode原文链接 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-ar...

    我是程序员小贱

扫码关注云+社区

领取腾讯云代金券