Discussion on Sherlock and Cost Challenge

4 months ago+ 2 comments

Here's a PHP solution to solve this problem:

<?php

function cost($B) {
    $n = count($B);

    // dp array where dp[0] means A[i] is 1 and dp[1] means A[i] is B[i]
    $dp = array_fill(0, 2, 0);

    for ($i = 1; $i < $n; $i++) {
        $prevDp0 = $dp[0];
        $prevDp1 = $dp[1];

        // When A[i] is 1
        $dp[0] = max(
            $prevDp0 + abs(1 - 1), // A[i-1] is 1
            $prevDp1 + abs(1 - $B[$i - 1]) // A[i-1] is B[i-1]
        );

        // When A[i] is B[i]
        $dp[1] = max(
            $prevDp0 + abs($B[$i] - 1), // A[i-1] is 1
            $prevDp1 + abs($B[$i] - $B[$i - 1]) // A[i-1] is B[i-1]
        );
    }

    // The result is the maximum value when A[n-1] is either 1 or B[n-1]
    return max($dp[0], $dp[1]);
}

// Example usage:
$B = [10, 1, 10, 1, 10];
echo cost($B); // Output: 36

?>

Explanation:

Dynamic Programming Table (dp):
- dp[0]: The maximum cost when A[i] is set to 1.
- dp[1]: The maximum cost when A[i] is set to B[i].
Transition between states:
- For each i from 1 to n-1, we update dp[0] and dp[1] based on the previous values:
  - If A[i] is 1, the cost can come from either A[i-1] being 1 or B[i-1].
  - If A[i] is B[i], the cost can come from either A[i-1] being 1 or B[i-1].
Final Result:
- The result will be the maximum value between dp[0] and dp[1] at the end of the array, which represents the maximum cost achievable by either setting A[n-1] to 1 or B[n-1].

This solution efficiently computes the desired result with a time complexity of O(n), making it suitable for large inputs within the constraints.

Explanation:

Cookie support is required to access HackerRank