Question

求数组的最大子数组的穷举法

#define SIZE 6
#include <iostream.h>
typedef struct {
int from;
int to;
int sum;
}SubMatrix[SIZE*(SIZE+1)/2],*subMatrix;

int main(){

SubMatrix SM;

subMatrix p=NULL;

int matrix[SIZE]={-1,4,2,2,5,-10};

for (int i=0;i<SIZE;i++){

for (int j=0;j<=i;j++){

SM[i*(i+1)/2+j].from=j;

SM[i*(i+1)/2+j].to=i;

SM[i*(i+1)/2+j].sum=0;

for(int cursor=j;cursor<=i;cursor++)

SM[i*(i+1)/2+j].sum+=matrix[cursor];

int temp=SM[0].sum;

if(SM[i*(i+1)/2+j].sum>=temp){

temp=SM[i*(i+1)/2+j].sum;

p=&SM[i*(i+1)/2+j];
}

}
}

/* for(int i=0;i<SIZE*(SIZE+1)/2;i++)

cout<<SM[i].sum<<SM[i].from<<SM[i].to<<endl;

cout<<"HELLO"<<endl;

*/
cout<<p->sum<<p->from<<p->to;

return 0;

}

请哪位好友帮我把上面的问题解决了
总是得不到正确的答案啊
所谓最大子数组是指在所有的连续下标的子数组中元素和最大的子数组
from指示起始下标
to是结束下标

若以下回答无法解决问题，邀请你更新回答

Answer 1

#define SIZE 6
#include <iostream.h>
typedef struct {
int from;
int to;
int sum;
}SubMatrix[SIZE*(SIZE+1)/2],*subMatrix;

int main(){

SubMatrix SM;

subMatrix p=NULL;

int temp;

int matrix[SIZE]={-1,4,2,2,5,-10};

for (int i=0;i<SIZE;i++){ // to

for (int j=0;j<=i;j++){ //from

SM[i*(i+1)/2+j].from=j;

SM[i*(i+1)/2+j].to=i;

SM[i*(i+1)/2+j].sum=0;

for(int cursor=j;cursor<=i;cursor++)
SM[i*(i+1)/2+j].sum+=matrix[cursor]; //calc sum

//int temp=SM[0].sum; //wrong, each time only compare to SM[0], not max
if (i==0 && j==0)
temp = SM[0].sum;

if(SM[i*(i+1)/2+j].sum>=temp){

temp=SM[i*(i+1)/2+j].sum;
p=&SM[i*(i+1)/2+j];
temp = SM[i*(i+1)/2+j].sum; //need this
}
}
}

/* for(int i=0;i<SIZE*(SIZE+1)/2;i++)

cout<<SM[i].sum<<SM[i].from<<SM[i].to<<endl;

cout<<"HELLO"<<endl;

*/
cout<<p->sum << " " <<p->from << " " <<p->to;

return 0;

}

答案为：13 1 4 正确