مساله:
جمع بیشترین زیر دنباله پشت سر هم از آرایه ای که به شما داده می شود را بدست آورید:
Max.sequence(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
// should be 6: {4, -1, 2, 1}حالت آسان زمانی است که لیست فقط از اعداد مثبت تشکیل شده باشد و حداکثر مجموع آن مجموع کل آرایه میشود. اگر لیست فقط از اعداد منفی تشکیل شده است، عدد 0 را برگردانید.
Description:
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
Max.sequence(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
// should be 6: {4, -1, 2, 1}Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
public class Max {
public static int sequence(int[] arr) {
int max_ending_here = 0, max_so_far = 0;
for (int v : arr) {
max_ending_here = Math.max(0, max_ending_here + v);
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
}public class Max {
public static int sequence(int[] arr) {
int m = 0, a = 0, s = 0;
for(int e : arr) {
s += e;
m = Math.min(s, m);
a = Math.max(a, s - m);
}
return a;
}
}public class Max {
public static int sequence(int[] arr) {
int cur = 0, max = 0;
for (int i : arr) {
cur = Math.max(0, cur + i);
max = Math.max(max, cur);
}
return max;
}
}public class Max {
public static int sequence(int[] arr) {
int sum = 0;
int max = 0;
for(int a : arr) {
sum += a;
max = Math.max(max, sum);
sum = Math.max(sum, 0);
}
return max;
}
}public class Max {
public static int sequence(int[] arr) {
int inst = 0, max = 0;
for (int i : arr) {
inst = Math.max(0, inst + i);
max = Math.max(max, inst);
}
return max;
}
}public class Max {
public static int sequence(int[] arr) {
int max_sum = 0;
for (int start_num = 0; start_num < arr.length; start_num++){
for (int end_num = start_num + 1; end_num < arr.length; end_num++) {
int this_sum = 0;
for (int index = start_num; index < end_num + 1; index++) {
this_sum += arr[index];
}
if (this_sum > max_sum) {
max_sum = this_sum;
}
}
}
return max_sum;
}
}
