Given an integer array nums and an integer k, modify the array in the following way:
i and replace nums[i] with -nums[i].You should apply this process exactly k times. You may choose the same index i multiple times.
Return the largest possible sum of the array after modifying it in this way.
Example 1:
Input: nums = [4,2,3], k = 1 Output: 5 Explanation: Choose index 1 and nums becomes [4,-2,3].
Example 2:
Input: nums = [3,-1,0,2], k = 3 Output: 6 Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].
Example 3:
Input: nums = [2,-3,-1,5,-4], k = 2 Output: 13 Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].
Constraints:
1 <= nums.length <= 104-100 <= nums[i] <= 1001 <= k <= 104program main
implicit none
integer, parameter :: n = 4
integer, parameter :: k = 1
integer, dimension(n) :: nums
integer :: i
integer :: max_sum
! Example 1
nums = (/ 4, 2, 3 /)
call solve(nums, k)
write (*, '(A, I0)') 'Example 1: ', sum(nums)
! Example 2
nums = (/ 3, -1, 0, 2 /)
call solve(nums, k)
write (*, '(A, I0)') 'Example 2: ', sum(nums)
! Example 3
nums = (/ 2, -3, -1, 5, -4 /)
call solve(nums, k)
write (*, '(A, I0)') 'Example 3: ', sum(nums)
contains
subroutine solve(nums, k)
implicit none
integer, intent(inout) :: nums(:)
integer, value :: k
integer :: i
do i = 1, k
call choose_index(nums)
end do
end subroutine solve
subroutine choose_index(nums)
implicit none
integer, intent(inout) :: nums(:)
integer :: i
call random_number(i)
i = int(i * size(nums)) + 1
nums(i) = -nums(i)
end subroutine choose_index
end program maintemp.f95:43:27:
43 | call random_number(i)
| 1
Error: ‘harvest’ argument of ‘random_number’ intrinsic at (1) must be REAL
temp.f95:11:4:
11 | nums = (/ 4, 2, 3 /)
| 1
Error: Different shape for array assignment at (1) on dimension 1 (4 and 3)
temp.f95:21:4:
21 | nums = (/ 2, -3, -1, 5, -4 /)
| 1
Error: Different shape for array assignment at (1) on dimension 1 (4 and 5)
module MaxSumAfterModifyingArray
implicit none
private
public :: max_sum_after_modifying_array
contains
function max_sum_after_modifying_array(nums, k) result(max_sum)
integer, intent(in) :: nums(:)
integer, intent(in) :: k
integer :: max_sum
integer :: i, j, index
integer :: sum
! Initialize variables
max_sum = 0
sum = 0
! Loop k times
do i = 1, k
! Find the maximum sum
do j = 1, size(nums)
sum = sum + nums(j)
if (sum > max_sum) then
max_sum = sum
index = j
end if
end do
! Replace the maximum value with its negative
nums(index) = -nums(index)
sum = 0
end do
! Return the maximum sum
max_sum = sum(nums)
end function max_sum_after_modifying_array
end module MaxSumAfterModifyingArray
! Test the function with the given examples
program test_max_sum_after_modifying_array
use MaxSumAfterModifyingArray
implicit none
integer, parameter :: nums1\[\] = \[4, 2, 3\]
integer, parameter :: nums2\[\] = \[3, -1, 0, 2\]
integer, parameter :: nums3\[\] = \[2, -3, -1, 5, -4\]
integer, parameter :: k1 = 1
integer, parameter :: k2 = 3
integer, parameter :: k3 = 2
integer :: max_sum
max_sum = max_sum_after_modifying_array(nums1, k1)
write (*,*) "Example 1:", max_sum
max_sum = max_sum_after_modifying_array(nums2, k2)
write (*,*) "Example 2:", max_sum
max_sum = max_sum_after_modifying_array(nums3, k3)
write (*,*) "Example 3:", max_sum
end program test_max_sum_after_modifying_array
temp.f95:36:9:
36 | max_sum = sum(nums)
| 1
Error: Unclassifiable statement at (1)
temp.f95:31:12:
31 | nums(index) = -nums(index)
| 1
Error: Dummy argument ‘nums’ with INTENT(IN) in variable definition context (assignment) at (1)
temp.f95:42:9:
42 | use MaxSumAfterModifyingArray
| 1
Fatal Error: Cannot open module file ‘maxsumaftermodifyingarray.mod’ for reading at (1): No such file or directory
compilation terminated.
def is_univalued(root, val=None):
if not root:
return True
if val is None:
val = root.val
return root.val == val and is_univalued(root.left, val) and is_univalued(root.right, val)
The algorithm first checks if the root node is null, if it is, the function returns true as an empty tree is uni-valued. If this is the first call to the function (indicated by default value for val), it sets the val to the root node's value. For all other calls, val is already set, and it only checks if the current node's value is equal to val. If it is equal, it recursively calls for the left and right sub-trees. If all calls return true, the tree is uni-valued, otherwise it's not.
bool isUnivalued(TreeNode* root, int val = -1) {
if (!root) return true;
if (val == -1) val = root->val;
return root->val == val && isUnivalued(root->left, val) && isUnivalued(root->right, val);
}
The algorithm first checks if the root node is null, if it is, the function returns true as an empty tree is uni-valued. If this is the first call to the function (indicated by default value for val), it sets the val to the root node's value. For all other calls, val is already set, and it only checks if the current node's value is equal to val. If it is equal, it recursively calls for the left and right sub-trees. If all calls return true, the tree is uni-valued, otherwise it's not.