iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 12
0
自我挑戰組

刷題記錄與人生分享系列 第 12

DAY12 Maximum Product Subarray

  • 分享至 

  • xImage
  •  

題目:

https://leetcode.com/problems/maximum-product-subarray/
給定一個陣列,找到連續的最大乘積

解題思路:

利用for迴圈透過3個變數temp、cur、last紀錄暫時現在與上次的數值,在相互比較後回傳。

C版本:

int maxProduct(int* nums, int numsSize) {
    int max=nums[0];
    int lastmax=nums[0];
    int lastmin=nums[0];
    int curmax,curmin;
    int temp1;
    int temp2;
    if(numsSize==1) return nums[0];
    for(int i=1;i<numsSize;i++)
    {
        temp1=lastmax*nums[i];
        temp2=lastmin*nums[i];
        curmax=temp1>temp2?temp1:temp2;
        curmax=curmax>nums[i]?curmax:nums[i];
        curmin=temp1>temp2?temp2:temp1;
        curmin=curmin>nums[i]?nums[i]:curmin;
        max=max>curmax?max:curmax;
        lastmax=curmax;
        lastmin=curmin;
    }
    return max;
}

Javascript版本:

var maxProduct = function(nums) {
    var max=nums[0];
    var lastmax=nums[0];
    var lastmin=nums[0];
    var curmax,curmin;
    var temp1;
    var temp2;
    if(nums.length==1) return nums[0];
    for(var i=1;i<nums.length;i++)
    {
        temp1=lastmax*nums[i];
        temp2=lastmin*nums[i];
        curmax=temp1>temp2?temp1:temp2;
        curmax=curmax>nums[i]?curmax:nums[i];
        curmin=temp1>temp2?temp2:temp1;
        curmin=curmin>nums[i]?nums[i]:curmin;
        max=max>curmax?max:curmax;
        lastmax=curmax;
        lastmin=curmin;
    }
    return max;
};

程式Github分享:

https://github.com/SIAOYUCHEN/leetcode

相似主題分享:

https://ithelp.ithome.com.tw/users/20100009/ironman/2500
https://ithelp.ithome.com.tw/users/20113393/ironman/2169
https://ithelp.ithome.com.tw/users/20107480/ironman/2435
https://ithelp.ithome.com.tw/users/20107195/ironman/2382
https://ithelp.ithome.com.tw/users/20119871/ironman/2210
https://ithelp.ithome.com.tw/users/20106426/ironman/2136

本日分享:

If you can’t find a reason for a while, the let slow down and enjoy the world by yourself, because smiling may be on the way.
如果暫時還找不到微笑的理由,那就放慢腳步享受這世界,因為微笑它可能正在來的路上。


上一篇
DAY11 Pascal's Triangle
下一篇
DAY13 Two Sum II - Input array is sorted
系列文
刷題記錄與人生分享34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言