public static void main(String[] args) {
int arr[]= {0,-1,2,-3,5,9,-5,10};
int max_ending_here=0;
int max_so_far=0;
int start =0;
int end=0;
for(int i=0;i< arr.length;i++)
{
max_ending_here=max_ending_here+arr[i];
if(max_ending_here<0)
{
max_ending_here=0;
}
if(max_so_far<max_ending_here){
max_so_far=max_ending_here;
}
}
System.out.println(max_so_far);
}
}
此程序使用{5,9，-5,10}生成子数组..在这种情况下为19的最大和。现在我必须找到此子数组的开始和结束索引..我该怎么做??
喜欢这个
public static void main(String[] args) {
int arr[]= {0,-1,2,-3,5,9,-5,10};
int max_ending_here=0;
int max_so_far=0;
int start =0;
int end=0;
for(int i=0;i< arr.length;i++){
max_ending_here=max_ending_here+arr[i];
if(max_ending_here<0)
{
start=i+1; //Every time it goes negative start from next index
max_ending_here=0;
}
else
end =i; //As long as its positive keep updating the end
if(max_so_far<max_ending_here){
max_so_far=max_ending_here;
}
}
System.out.println(max_so_far);
}
好的，以上解决方案中出现了问题，如Steve P所指出。这是另一种适用于所有人的解决方案
public static int[] compareSub(int arr[]){
int start=-1;
int end=-1;
int max=0;
if(arr.length>0){
//Get that many array elements and compare all of them.
//Then compare their max to the overall max
start=0;end=0;max=arr[0];
for(int arrSize=1;arrSize<arr.length;arrSize++){
for(int i=0;i<arr.length-arrSize+1;i++){
int potentialMax=sumOfSub(arr,i,i+arrSize);
if(potentialMax>max){
max=potentialMax;
start=i;
end=i+arrSize-1;
}
}
}
}
return new int[]{start,end,max};
}
public static int sumOfSub(int arr[],int start,int end){
int sum=0;
for(int i=start;i<end;i++)
sum+=arr[i];
return sum;
}
C中的O（n）解为：-
void maxsumindex(int arr[], int len)
{
int maxsum = INT_MIN, cur_sum = 0, start=0, end=0, max = INT_MIN, maxp = -1, flag = 0;
for(int i=0;i<len;i++)
{
if(max < arr[i]){
max = arr[i];
maxp = i;
}
cur_sum += arr[i];
if(cur_sum < 0)
{
cur_sum = 0;
start = i+1;
}
else flag = 1;
if(maxsum < cur_sum)
{
maxsum = cur_sum;
end = i;
}
}
//This is the case when all elements are negative
if(flag == 0)
{
printf("Max sum subarray = {%d}\n",arr[maxp]);
return;
}
printf("Max sum subarray = {");
for(int i=start;i<=end;i++)
printf("%d ",arr[i]);
printf("}\n");
}
这里是使用Kadane算法的Go解决方案
func maxSubArr(A []int) (int, int, int) {
start, currStart, end, maxSum := 0, 0, 0, A[0]
maxAtI := A[0]
for i := 1; i < len(A); i++ {
if maxAtI > 0 {
maxAtI += A[i]
} else {
maxAtI = A[i]
currStart = i
}
if maxAtI > maxSum {
maxSum = maxAtI
start = currStart
end = i
}
}
return start, end, maxSum
}
对kadane的算法稍作修改即可完成工作：
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int start=0;
int end=0;
int s=0;
int curr_max=a[0];
int abs_max=a[0];
for(int i=1;i<n;i++){
if(a[i]>curr_max+a[i])
s=i;
curr_max=max(curr_max+a[i],a[i]);
if(curr_max>abs_max){
abs_max=curr_max;
start=s;
end=i;
}
}
cout<<abs_max<<" "<<start<<" "<<end;
}
这是用于解决此问题的C程序。我认为所有语言的逻辑都相同，因此我发布了此答案。
void findMaxSubArrayIndex(){
int n,*a;
int start=0,end=0,curr_max=0,prev_max=0,start_o=0,i;
scanf("%d",&n);
a = (int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++) scanf("%d",a+i);
prev_max = a[0];
for(i=0; i<n; i++){
curr_max += a[i];
if(curr_max < 0){
start = i+1;
curr_max = 0;
}
else if(curr_max > prev_max){
end = i;
start_o = start;
prev_max = curr_max;
}
}
printf("%d %d \n",start_o,end);
}
这里是maxsubarray的算法：
public class MaxSubArray {
public static void main(String[] args) {
int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
//int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int[] intArr={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr);
}
public static void findMaxSubArray(int[] inputArray){
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = Integer.MIN_VALUE;
int cumulativeSum= 0;
int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
int eachArrayItem = inputArray[currentIndex];
cumulativeSum+=eachArrayItem;
if(cumulativeSum>maxSum){
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
System.out.println("Max sum : "+maxSum);
System.out.println("Max start index : "+maxStartIndex);
System.out.println("Max end index : "+maxEndIndex);
}
}
修复卡尔·萨尔达尼亚解决方案：
int max_ending_here = 0;
int max_so_far = 0;
int _start = 0;
int start = 0;
int end = -1;
for(int i=0; i<array.length; i++) {
max_ending_here = max_ending_here + array[i];
if (max_ending_here < 0) {
max_ending_here = 0;
_start = i+1;
}
if (max_ending_here > max_so_far) {
max_so_far = max_ending_here;
start = _start;
end = i;
}
}
这个问题尚不清楚，但我猜一个“子数组”是arr对象的一半。
这样的la脚方法
public int sum(int[] arr){
int total = 0;
for(int index : arr){
total += index;
}
return total;
}
public void foo(){
int arr[] = {0,-1,2,-3,5,9,-5,10};
int subArr1[] = new int[(arr.length/2)];
int subArr2[] = new int[(arr.length/2)];
for(int i = 0; i < arr.length/2; i++){
// Lazy hack, might want to double check this...
subArr1[i] = arr[i];
subArr2[i] = arr[((arr.length -1) -i)];
}
int sumArr1 = sum(subArr1);
int sumArr2 = sum(subArr2);
}
我认为如果arr包含奇数个元素，则可能无法正常工作。
如果您希望获得更高级别的支持，请将原始数组转换为List对象
List<Integer> list = Arrays.asList(arr);
通过这种方式，您可以访问集合对象的功能。
同样，如果有时间，请查看称为reduce的高阶函数。您将需要一个支持功能编程的库。番石榴或lambdaJ可能有一种还原方法。我知道apache-commons缺少一个，除非您想将其组合在一起。
这是python中的解决方案-Kadane's algorithm扩展为打印开始/结束索引
def max_subarray(array):
max_so_far = max_ending_here = array[0]
start_index = 0
end_index = 0
for i in range(1, len(array) -1):
temp_start_index = temp_end_index = None
if array[i] > (max_ending_here + array[i]):
temp_start_index = temp_end_index = i
max_ending_here = array[i]
else:
temp_end_index = i
max_ending_here = max_ending_here + array[i]
if max_so_far < max_ending_here:
max_so_far = max_ending_here
if temp_start_index != None:
start_index = temp_start_index
end_index = i
print max_so_far, start_index, end_index
if __name__ == "__main__":
array = [-2, 1, -3, 4, -1, 2, 1, 8, -5, 4]
max_subarray(array)
public static void maxSubArray(int []arr){
int sum=0,j=0;
int temp[] = new int[arr.length];
for(int i=0;i<arr.length;i++,j++){
sum = sum + arr[i];
if(sum <= 0){
sum =0;
temp[j] = -1;
}else{
temp[j] = i;
}
}
rollback(temp,arr);
}
public static void rollback(int [] temp , int[] arr){
int s =0,start=0 ;
int maxTillNow = 0,count =0;
String str1 = "",str2="";
System.out.println("============");
// find the continuos index
for(int i=0;i<temp.length;i++){
if(temp[i] != -1){
s += arr[temp[i]];
if(s > maxTillNow){
if(count == 0){
str1 = "" + start;
}
count++;
maxTillNow = s;
str2 = " " + temp[i];
}
}else{
s=0;
count =0;
if(i != temp.length-1)
start = temp[i+1];
}
}
System.out.println("Max sum will be ==== >> " + maxTillNow);
System.out.print("start from ---> "+str1 + " end to --- >> " +str2);
}
public void MaxSubArray(int[] arr)
{
int MaxSoFar = 0;
int CurrentMax = 0;
int ActualStart=0,TempStart=0,End = 0;
for(int i =0 ; i<arr.Length;i++)
{
CurrentMax += arr[i];
if(CurrentMax<0)
{
CurrentMax = 0;
TempStart = i + 1;
}
if(MaxSoFar<CurrentMax)
{
MaxSoFar = CurrentMax;
ActualStart = TempStart;
End = i;
}
}
Console.WriteLine(ActualStart.ToString()+End.ToString());
}
我唯一要添加的内容（在此处发布的几个解决方案中是要覆盖所有整数均为负的情况，在这种情况下，max子数组将只是max元素。做到这一点非常容易..只需在迭代过程中跟踪max元素和max元素的索引即可。如果max元素为负，则返回其索引。
也有可能发生溢出的情况。我看过算法测试，而不是考虑在内。IE，假设MAXINT是元素之一，并且您尝试将其添加到其中。我相信某些Codility（编码采访筛选器）测试会将这一点考虑在内。