You are given an integer array prices where prices[i] is the price of the ith item in a shop.
There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.
Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.
Example 1:
Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. For items 3 and 4 you will not receive any discount at all.
Example 2:
Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Explanation: In this case, for all items, you will not receive any discount at all.
Example 3:
Input: prices = [10,1,1,6] Output: [9,0,1,6]
Constraints:
1 <= prices.length <= 5001 <= prices[i] <= 1000The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
program main
implicit none
integer, parameter :: n = 5
integer, dimension(n) :: prices = (/ 8, 4, 6, 2, 3 /)
integer, dimension(n) :: answer
call solve(prices, answer)
write (*, '(A)') 'Answer:'
write (*, '(*(I0, 1X))') answer
contains
subroutine solve(prices, answer)
implicit none
integer, intent(in) :: prices(:)
integer, intent(out) :: answer(:)
integer :: i, j, k
do i = 1, size(prices)
j = i + 1
do while (j <= size(prices) .and. prices(j) <= prices(i))
j = j + 1
end do
if (j <= size(prices)) then
k = j - 1
answer(i) = prices(i) - prices(k)
else
answer(i) = prices(i)
end if
end do
end subroutine solve
end program mainAnswer: 8 0 6 0 3
module discount
implicit none
contains
function calculate_discount(prices) result(answer)
integer, intent(in) :: prices(:)
integer :: answer(size(prices))
! Local variables
integer :: i, j, discount
! Calculate the discount for each item
do i = 1, size(prices)
! Find the minimum index j such that j > i and prices(j) <= prices(i)
j = minloc(prices(i+1:), 1) + i
! Calculate the discount
discount = prices(j) - prices(i)
! Set the final price for the item
answer(i) = prices(i) - discount
end do
end function calculate_discount
end module discount
program main
use discount
implicit none
! Test the function with the given examples
call test_discount(8, 4, 6, 2, 3, 4, 2, 4, 2, 3)
call test_discount(1, 2, 3, 4, 5)
call test_discount(10, 1, 1, 6)
contains
subroutine test_discount(prices, expected)
integer, intent(in) :: prices(:)
integer, intent(in) :: expected(:)
! Local variables
integer :: answer(size(prices))
! Calculate the discount for the items
answer = calculate_discount(prices)
! Check if the answer is correct
if (any(answer .ne. expected)) then
write (*,*) "Test failed!"
else
write (*,*) "Test passed!"
end if
end subroutine test_discount
end program main
temp.f95:39:19:
39 | call test_discount(8, 4, 6, 2, 3, 4, 2, 4, 2, 3)
| 1
Error: Rank mismatch in argument ‘prices’ at (1) (rank-1 and scalar)
temp.f95:40:19:
40 | call test_discount(1, 2, 3, 4, 5)
| 1
Error: Rank mismatch in argument ‘prices’ at (1) (rank-1 and scalar)
temp.f95:41:19:
41 | call test_discount(10, 1, 1, 6)
| 1
Error: Rank mismatch in argument ‘prices’ at (1) (rank-1 and scalar)
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def maxSumBST(root):
def helper(node):
if not node:
return float('inf'), float('-inf'), 0, True
left_min, left_max, left_sum, is_left_bst = helper(node.left)
right_min, right_max, right_sum, is_right_bst = helper(node.right)
if is_left_bst and is_right_bst and node.val > left_max and node.val < right_min:
sum_ = node.val + left_sum + right_sum
max_sum[0] = max(max_sum[0], sum_)
return min(node.val, left_min), max(node.val, right_max), sum_, True
return 0, 0, 0, False
max_sum = [0]
helper(root)
return max_sum[0]
We perform a post-order traversal of the tree, as we need information about both the left and right children of a node to determine if the current node's subtree is also a BST.
For every node, we recursively call the helper function for its left and right children, getting their min key, max key, sum of keys, and a boolean representing if the subtree rooted at these children is a BST or not.
We then check if the current node's subtree can be considered as a BST. If it is true, we update the maximum sum if needed using the sum of the keys in the current subtree. In any case, we return the minimum and maximum keys, the sum of the keys, and a boolean indicating if the current subtree is a BST or not.
After the post-order traversal is complete, we return the maximum sum found.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int maxSumBST(TreeNode* root) {
int max_sum = 0;
helper(root, max_sum);
return max_sum;
}
tuple<int, int, int, bool> helper(TreeNode* node, int& max_sum) {
if (node == nullptr) {
return {INT_MAX, INT_MIN, 0, true};
}
auto[left_min, left_max, left_sum, is_left_bst] = helper(node->left, max_sum);
auto[right_min, right_max, right_sum, is_right_bst] = helper(node->right, max_sum);
if (is_left_bst && is_right_bst && node->val > left_max && node->val < right_min) {
int sum = node->val + left_sum + right_sum;
max_sum = max(max_sum, sum);
return {min(node->val, left_min), max(node->val, right_max), sum, true};
}
return {0, 0, 0, false};
}
We perform a post-order traversal of the tree, as we need information about both the left and right children of a node to determine if the current node's subtree is also a BST.
For every node, we recursively call the helper function for its left and right children, getting their min key, max key, sum of keys, and a boolean representing if the subtree rooted at these children is a BST or not.
We then check if the current node's subtree can be considered as a BST. If it is true, we update the maximum sum if needed using the sum of the keys in the current subtree. In any case, we return the minimum and maximum keys, the sum of the keys, and a boolean indicating if the current subtree is a BST or not.
After the post-order traversal is complete, we return the maximum sum found.