浙大版《数据结构(第2版)》题目集 实例1.1 最大子列和问题 (20分)
程序员文章站
2022-06-10 19:20:31
...
6
-2 11 -4 13 -5 -2
#include <iostream>
using namespace std;
struct list
{
int a;
struct list *next;
};
int main()
{
int n;
int max = 0, now = 0;
cin >> n;
struct list *head;
struct list *p1, *p2;
head = p2 = new (struct list);
cin >> p2->a;
for (int i = 0; i < n; i++) //输入被测试数据
{
p1 = new (struct list);
cin >> p1->a;
p2->next = p1;
p2 = p1;
}
p2->next = NULL;
p1 = head;
while (p1 != NULL) //遍历链表 找出最大子列和
{
now += p1->a;
if (now <= 0)
now = 0;
if (now > max)
max = now;
p1 = p1->next;
}
while (p1 != NULL) //释放内存
{
p2 = p1->next;
delete p1;
p1 = p2;
}
cout << max;
return 0;
}