• Lớp 11
  • Tin Học
  • Mới nhất
2 đáp án
23 lượt xem

Cho mảng các số nguyên arr và số nguyên k, bạn hãy tìm mảng con có tổng lớn nhất mà nhỏ hơn hoặc bằng k trong arr, với định nghĩa mảng con của arr là mảng chứa các phần tử liên tiếp nằm trong arr. Sau đó trả về tổng của mảng con này. Đầu vào luôn đảm bảo có ít nhất một mảng con có tổng nhỏ hơn hoặc bằng k. Ví dụ: Với arr = [1, 4, 1, 4, 5, 3], k = 7 thì output là maxSum(arr, k) = 6. Giải thích: mảng con có tổng lớn nhất mà nhỏ hơn hoặc bằng 7 trong arr là [1, 4, 1] và tổng của mảng này là 6. Ngoài ra không thể tìm được mảng con có tổng là 7. Với arr = [1, 2, 3, 4, 5], k = 11 thì output là maxSum(arr, k) = 10. Giải thích: mảng con có tổng lớn nhất mà nhỏ hơn hoặc bằng 11 là [1, 2, 3, 4] và tổng của mảng này là 10. Ngoài ra không thể tìm được mảng con có tổng là 11. Với arr = [2, 4, 6, 8], k = 7 thì output là maxSum(arr, k) = 6. Giải thích: hai mảng con có tổng lớn nhất là [2, 4] và [6]. Ngoài ra không thể tìm được mảng con có tổng là 7. Đầu vào/Đầu ra: [Thời gian chạy] 0.5s với C/C++, 3s với Java và C#, 4s với Python, Go và JavaScript. [Đầu vào] Array of Integer arr 1 <= arr.length <= 100000 1 <= arr[i] <= 100000 [Đầu vào] Integer k 1 <= k <= 109 [Đầu ra] Integer kết quả là tổng lớn nhất nhỏ hơn hoặc bằng k

1 đáp án
47 lượt xem