2873. حداکثر مقدار یک سه گانه سفارش داده شده I

2873. حداکثر مقدار یک سه گانه سفارش داده شده I

مشکل: آسان

مباحث: Array

به شما داده می شود 0-شاخص آرایه عدد صحیح numsبشر

بازگشت حداکثر ارزش در تمام سه سه گانه شاخص ها (i, j, k) به گونه ای که i < j < kبشر اگر همه این سه گانه ارزش منفی دارند ، بازگردید 0بشر

در ارزش سه گانه شاخص ها (i, j, k) برابر است با (nums[i] - nums[j]) * nums[k]بشر

مثال 1:

• ورودی: nums = [12,6,1,2,7]
• خروجی: 77
• توضیح: مقدار سه گانه (0 ، 2 ، 4) (تعداد) است[0] – شماره[2]) * تعداد[4] = 77
  • می توان نشان داد که هیچ سه گانه سفارش داده شده با ارزش بیشتر از 77 وجود ندارد.

مثال 2:

• ورودی: nums = [1,10,3,4,19]
• خروجی: 133
• توضیح: مقدار سه گانه (1 ، 2 ، 4) (شماره ها است[1] – شماره[2]) * تعداد[4] = 133.
  • می توان نشان داد که هیچ سه گانه سفارش داده شده با ارزش بیشتر از 133 وجود ندارد.

مثال 3:

• ورودی: nums = [1,2,3]
• خروجی: 0
• توضیح: تنها سه گانه سفارش داده شده (0 ، 1 ، 2) دارای مقدار منفی (NUMS است[0] – شماره[1]) * تعداد[2] = -3. از این رو ، پاسخ 0 خواهد بود.

محدودیت ها:

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 106

نکته:

1. برای یافتن تمام سه گانه از سه حلقه تو در تو استفاده کنید.

راه حل:

ما باید حداکثر ارزش همه سه گانه سفارش داده شده (i ، j ، k) را پیدا کنیم به گونه ای که من در یک آرایه معین

رویکرد

بینش کلیدی برای بهینه سازی راه حل این است که تشخیص دهد که برای هر جفت (i ، j) ، حداکثر مقدار ممکن سه گانه (i ، j ، k) را می توان با حداکثر مقدار تعداد nums تعیین کرد[k] برای k> j. این به ما اجازه می دهد تا حداکثر مقدار را در سمت راست هر شاخص J ، که مشکل را از پیچیدگی زمان O (n^3) به O (n^2) کاهش می دهد ، پیش بینی کنیم.

1. مقادیر حداکثر را پیش بینی کنید: یک آرایه ایجاد کنید max_right جایی که هر عنصر در فهرست j حداکثر مقدار شماره از فهرست j+1 تا انتهای آرایه است. این به تعیین سریع حداکثر تعداد ممکن کمک می کند[k] برای هر j داده شده
2. تکرار بیش از جفت (من ، j): برای هر جفت معتبر (i ، j) که در آن من max_right آرایه برای یافتن حداکثر مقدار ممکن سه گانه (i ، j ، k) به طور کارآمد.
3. تعیین نتیجه: حداکثر مقدار به دست آمده از کلیه سه گانه معتبر را پیگیری کنید. اگر حداکثر مقدار غیر مثبت است ، 0 را برگردانید. در غیر این صورت ، حداکثر مقدار را برگردانید.

بیایید این راه حل را در PHP پیاده سازی کنیم: 2873. حداکثر مقدار یک سه گانه سفارش داده شده I

/**
 * @param Integer[] $nums
 * @return Integer
 */
function maximumTripletValue($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [12,6,1,2,7];
$nums2 = [1,10,3,4,19];
$nums3 = [1,2,3];

echo maximumTripletValue($nums1) . "\n"; // Output: 77
echo maximumTripletValue($nums2) . "\n"; // Output: 133
echo maximumTripletValue($nums3) . "\n"; // Output: 0
?>

توضیح:

1. مقادیر حداکثر را پیش بینی کنید: max_right آرایه با تکرار از انتهای آرایه تا ابتدا ساخته می شود. برای هر فهرست j ، max_right[j] حداکثر مقدار فرعی را از J+1 تا انتها شروع می کند. این اجازه می دهد تا (1) دسترسی به حداکثر تعداد ممکن[k] برای هر j
2. تکرار بیش از جفت (من ، j): برای هر جفت (i ، j) ، مقدار سه گانه با استفاده از حداکثر مقدار از پیش تعیین شده از محاسبه می شود max_right[j]بشر این امر از لزوم تکرار بیش از K به صراحت جلوگیری می کند و باعث کاهش پیچیدگی زمان می شود.
3. محاسبه نتیجه: حداکثر مقدار به دست آمده از همه جفت های معتبر (I ، J) بررسی می شود. اگر مثبت باشد ، بازگردانده می شود. در غیر این صورت ، 0 بازگردانده می شود ، اطمینان حاصل می کنیم که ما موردی را که تمام مقادیر سه گانه به طور مؤثر غیر مثبت هستند ، اداره می کنیم.

این رویکرد با استفاده از مقادیر پیش فرض ، پیچیدگی مشکل را به طور مؤثر کاهش می دهد ، و این امر باعث می شود که اندازه های ورودی بزرگتر در محدوده زمانی قابل قبول انجام شود.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: