Viết chương trình tính tổng lớn nhất của một chuổi con liên tiếp trong mảng một chiều.
Mình xin giới thiệu thuật toán Kadane’s Algorithm:
|
B1: Khởi tạo: B2: Loop qua mỗi phần tử của mảng a[i] B3: return max_so_far |
Ý tưởng của thuật toán là tìm tổng của tất các cả các mảng con có giá trị dương(max_ending_here). Cứ mỗi lần tìm được tổng của một mảng con thì tiến hành lưu lại trong max_so_far nếu giá trị mới lớn hơn giá trị hiện tại.
Ví dụ
Cho mảng a:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = Minvaue
max_ending_here = 0
for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
gán max_ending_here = 0 vì max_ending_here < 0
for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
gán max_ending_here = 0 vì max_ending_here < 0
for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
gán max_so_far = 4 vì max_ending_here > max_so_far
for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3
for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1
for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2
for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
gán max_so_far = 7 vì max_ending_here > max_so_far
for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4
|
Implementation
public class Main {
public static void main(String[] args) {
int[] a = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum contiguous sum is " +
maxSubArraySum(a));
}
static int maxSubArraySum(int a[]) {
int size = a.length;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}
| Output: Maximum contiguous sum is 7 |