Đề bài:
Cho một mảng số nguyên `nums`, tìm subarray có tổng lớn nhất và trả về tổng của nó.
Ví dụ 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Giải thích: Subarray [4,-1,2,1] có tổng lớn nhất là 6.
Ví dụ 2:
Input: nums = [1] Output: 1 Giải thích: Subarray [1] có tổng lớn nhất là 1.
Ví dụ 3:
Input: nums = [5,4,-1,7,8] Output: 23 Giải thích: Subarray [5,4,-1,7,8] có tổng lớn nhất là 23.
Ràng buộc:
- 1 <= độ dài của mảng nums <= 10^5
- -10^4 <= nums[i] <= 10^4
Cách 1: 1D DP
Giải thích thuật toán bằng C ++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// dp[i] := max sum subarray ending w/ i
vector<int> dp(nums.size());
dp[0] = nums[0];
for (int i = 1; i < nums.size(); ++i)
dp[i] = max(nums[i], dp[i - 1] + nums[i]);
return ranges::max(dp);
}
};
Đây là một đoạn mã C++ để tìm subarray có tổng lớn nhất trong một mảng số nguyên `nums` bằng thuật toán Dynamic Programming (DP).
Hàm `maxSubArray` nhận đầu vào là một vector `nums` và trả về tổng lớn nhất của subarray.
Trong hàm `maxSubArray`, một vector `dp` được khởi tạo có cùng kích thước với `nums`. `dp[i]` đại diện cho tổng lớn nhất của subarray kết thúc tại phần tử thứ `i` trong `nums`.
Gán `dp[0]` bằng `nums[0]` là giá trị đầu tiên trong `nums`.
Sau đó, vòng lặp `for` được sử dụng để tính toán giá trị `dp[i]` cho các phần tử `nums[i]` từ `1` đến `nums.size() – 1`. Để tính giá trị `dp[i]`, ta so sánh `nums[i]` với `dp[i – 1] + nums[i]` và lấy giá trị lớn nhất để cập nhật `dp[i]`.
Cuối cùng, hàm `maxSubArray` trả về giá trị lớn nhất trong vector `dp`, đại diện cho tổng lớn nhất của subarray.
Đây là một cách tiếp cận DP để giải quyết bài toán tìm subarray có tổng lớn nhất, trong đó ta tận dụng thông tin về các subarray đã tính toán trước đó để tính toán subarray kết thúc tại mỗi phần tử.
Giải thích thuật toán bằng Java
class Solution {
public int maxSubArray(int[] nums) {
// dp[i] := the maximum sum subarray ending with i
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; ++i)
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
return Arrays.stream(dp).max().getAsInt();
}
}
Giải thích thuật toán bằng Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# dp[i] := the maximum sum subarray ending with i
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp)
Cách 2: O(1) DP
Giải thích thuật toán bằng C ++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
int sum = 0;
for (const int num : nums) {
sum = max(num, sum + num);
ans = max(ans, sum);
}
return ans;
}
};
Đoạn mã trên triển khai thuật toán để tìm dãy con liên tiếp có tổng lớn nhất trong một mảng `nums`.
Thuật toán này hoạt động như sau:
1. Khởi tạo biến `ans` với giá trị `INT_MIN` (giá trị nhỏ nhất có thể lưu trữ trong kiểu dữ liệu `int`) để lưu trữ tổng lớn nhất của dãy con.
2. Khởi tạo biến `sum` với giá trị 0 để lưu trữ tổng hiện tại của một dãy con.
3. Duyệt qua từng phần tử `num` trong mảng `nums`.
– Tại mỗi phần tử, ta cập nhật `sum` bằng cách lấy giá trị lớn nhất giữa `num` và `sum + num`. Điều này có ý nghĩa là ta sẽ kiểm tra xem có nên bắt đầu một dãy con mới từ `num` hay tiếp tục dãy con hiện tại bằng cách thêm `num` vào.
– Tiếp theo, ta cập nhật `ans` bằng cách lấy giá trị lớn nhất giữa `ans` và `sum`. Điều này đảm bảo `ans` luôn lưu giữ tổng lớn nhất đã được tìm thấy cho đến thời điểm hiện tại.
4. Sau khi duyệt qua tất cả các phần tử, ta trả về giá trị `ans` là tổng lớn nhất của một dãy con trong mảng `nums`.
Thuật toán này sử dụng một phương pháp gọi là “Kadane’s algorithm” để tìm dãy con có tổng lớn nhất. Ý tưởng chính của thuật toán là duyệt qua từng phần tử và cập nhật tổng hiện tại của dãy con bằng cách so sánh tổng hiện tại với phần tử hiện tại hoặc tổng hiện tại cộng với phần tử hiện tại. Bằng cách lưu giữ giá trị tổng lớn nhất đã tìm thấy cho đến thời điểm hiện tại, ta có thể tìm ra tổng lớn nhất của một dãy con trong mảng.
Giải thích thuật toán bằng Java
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int sum = 0;
for (final int num : nums) {
sum = Math.max(num, sum + num);
ans = Math.max(ans, sum);
}
return ans;
}
}
Giải thích thuật toán bằng Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = -math.inf
summ = 0
for num in nums:
summ = max(num, summ + num)
ans = max(ans, summ)
return ans
Cách 3: Divide and Conquer
Giải thích thuật toán bằng C ++
struct T {
int maxSubarraySumLeft; // The subarray starts from the first number.
int maxSubarraySumRight; // The subarray ends in the last number.
int maxSubarraySum;
int sum;
};
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return divideAndConquer(nums, 0, nums.size() - 1).maxSubarraySum;
}
private:
T divideAndConquer(const vector<int>& nums, int l, int r) {
if (l == r)
return {nums[l], nums[l], nums[l], nums[l]};
const int m = (l + r) / 2;
const T t1 = divideAndConquer(nums, l, m);
const T t2 = divideAndConquer(nums, m + 1, r);
const int maxSubarraySumLeft =
max(t1.maxSubarraySumLeft, t1.sum + t2.maxSubarraySumLeft);
const int maxSubarraySumRight =
max(t1.maxSubarraySumRight + t2.sum, t2.maxSubarraySumRight);
const int maxSubarraySum =
max({t1.maxSubarraySumRight + t2.maxSubarraySumLeft, t1.maxSubarraySum,
t2.maxSubarraySum});
const int sum = t1.sum + t2.sum;
return {maxSubarraySumLeft, maxSubarraySumRight, maxSubarraySum, sum};
}
};
Đoạn mã trên triển khai thuật toán “Divide and Conquer” để tìm dãy con liên tiếp có tổng lớn nhất trong một mảng `nums`.
Thuật toán này hoạt động như sau:
1. Định nghĩa một cấu trúc `T` để lưu trữ thông tin về dãy con tại mỗi node của cây đệ quy.
– `maxSubarraySumLeft`: Tổng lớn nhất của dãy con bắt đầu từ phần tử đầu tiên.
– `maxSubarraySumRight`: Tổng lớn nhất của dãy con kết thúc tại phần tử cuối cùng.
– `maxSubarraySum`: Tổng lớn nhất của dãy con trong mảng.
– `sum`: Tổng của các phần tử trong mảng.
2. Trong lớp `Solution`, có một phương thức `maxSubArray` nhận vào một mảng `nums` và trả về tổng lớn nhất của dãy con.
– Phương thức này gọi phương thức `divideAndConquer` để thực hiện phân chia và chinh phục.
3. Phương thức `divideAndConquer` được gọi đệ quy để giải quyết bài toán.
– Nếu chỉ có một phần tử trong mảng (điều kiện `l == r`), ta trả về một cấu trúc `T` với tất cả các trường bằng giá trị của phần tử đó.
– Ngược lại, ta tìm điểm giữa mảng (`m = (l + r) / 2`) và thực hiện đệ quy cho hai nửa mảng.
– Kết quả của hai đệ quy được lưu trữ trong hai biến `t1` và `t2`.
– Từ `t1` và `t2`, ta tính toán các giá trị tương ứng cho cấu trúc `T` của node hiện tại.
+ `maxSubarraySumLeft` được chọn là giá trị lớn nhất giữa `t1.maxSubarraySumLeft` và `t1.sum + t2.maxSubarraySumLeft`. Điều này đảm bảo dãy con bắt đầu từ phần tử đầu tiên sẽ nằm hoàn toàn trong nửa trái hoặc cắt qua phần tử giữa.
+ `maxSubarraySumRight` được chọn là giá trị lớn nhất giữa `t1.maxSubarraySumRight + t2.sum` và `t2.maxSubarraySumRight`. Điều này đảm bảo dãy con kết thúc tại phần tử cuối cùng sẽ nằm hoàn toàn trong nửa phải hoặc cắt qua phần tử giữa.
+ `maxSubarraySum` được chọn là giá trị lớn nhất giữa `t1.maxSubarraySumRight + t2.maxSubarraySumLeft`, `t1.maxSubarraySum` và `t2.maxSubarraySum`. Điều này đảm bảo ta có thể lấy dãy con từ cả hai nửa mảng hoặc chỉ từ một nửa.
+ `sum` là tổng của tất cả các phần tử trong mảng.
4. Sau khi đệ quy hoàn tất và trả về kết quả của nút gốc, phương thức `maxSubArray` trả về giá trị `maxSubarraySum` của kết quả đó.
Thuật toán “Divide and Conquer” này chia mảng ban đầu thành các mảng nhỏ hơn, giải quyết các mảng con và kết hợp kết quả để tìm ra dãy con có tổng lớn nhất. Bằng cách chiamảng thành các mảng con, thuật toán giải quyết vấn đề theo cách đệ quy và kết hợp các kết quả con để tìm ra dãy con có tổng lớn nhất.
Giải thích thuật toán bằng Java
class Solution {
public int maxSubArray(int[] nums) {
return divideAndConquer(nums, 0, nums.length - 1).maxSubarraySum;
}
private T divideAndConquer(int[] nums, int l, int r) {
if (l == r)
return new T(nums[l], nums[l], nums[l], nums[l]);
final int m = (l + r) / 2;
final T t1 = divideAndConquer(nums, l, m);
final T t2 = divideAndConquer(nums, m + 1, r);
final int maxSubarraySumLeft = Math.max(t1.maxSubarraySumLeft, t1.sum + t2.maxSubarraySumLeft);
final int maxSubarraySumRight =
Math.max(t1.maxSubarraySumRight + t2.sum, t2.maxSubarraySumRight);
final int maxSubarraySum = Math.max(t1.maxSubarraySumRight + t2.maxSubarraySumLeft,
Math.max(t1.maxSubarraySum, t2.maxSubarraySum));
final int sum = t1.sum + t2.sum;
return new T(maxSubarraySumLeft, maxSubarraySumRight, maxSubarraySum, sum);
}
private record T(int maxSubarraySumLeft, // The subarray starts from the first number.
int maxSubarraySumRight, // The subarray ends in the last number.
int maxSubarraySum, int sum) {}
}
Giải thích thuật toán bằng Python
from dataclasses import dataclass
@dataclass(frozen=True)
class T:
maxSubarraySumLeft: int # The subarray starts from the first number.
maxSubarraySumRight: int # The subarray ends in the last number.
maxSubarraySum: int
summ: int
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def divideAndConquer(l: int, r: int) -> T:
if l == r:
return T(nums[l], nums[l], nums[l], nums[l])
m = (l + r) // 2
t1 = divideAndConquer(l, m)
t2 = divideAndConquer(m + 1, r)
maxSubarraySumLeft = max(t1.maxSubarraySumLeft,
t1.summ + t2.maxSubarraySumLeft)
maxSubarraySumRight = max(
t1.maxSubarraySumRight + t2.summ, t2.maxSubarraySumRight)
maxSubarraySum = max(t1.maxSubarraySumRight +
t2.maxSubarraySumLeft, t1.maxSubarraySum, t2.maxSubarraySum)
summ = t1.summ + t2.summ
return T(maxSubarraySumLeft, maxSubarraySumRight, maxSubarraySum, summ)
return divideAndConquer(0, len(nums) - 1).maxSubarraySum
0 / 5 - (0 Đánh Giá)