结对开发Ⅴ——循环一维数组求和最大的子数组

 1 // 一维数组.cpp : Defines the entry point for the console application.
 2 // 袁佩佩 于海洋
 3 
 4 #include "stdafx.h"
 5 #include<iostream.h>
 6 #define num 5
 7 /*链表数据结构*/
 8 typedef struct LNode
 9 {
10     int data;
11     struct LNode *next;
12 }LNode,*LinkList;
13 /*链表的初始化*/
14 void InitList(LinkList &L)
15 {
16     L=new LNode;
17     L->next=NULL;
18 }
19 /*链表数据的插入*/
20 void InsertList(LinkList &L)//建立循环链表
21 {
22     LNode *head,*temp;
23     head=L;
24     cout<<"请输入"<<num<<"个数字：";
25     for(int i=0;i<num;i++)
26     {
27         temp=new LNode;
28         cin>>temp->data;
29         temp->next=NULL;
30         head->next=temp;
31         head=head->next;
32     }
33     head->next=L->next;                //首尾相连，建立循环链表
34 }
35 void output(LinkList L)
36 {
37     for(int i=0;i<num;i++)
38     {
39         cout<<L->next->data<<" ";
40         L=L->next;
41     }
42 }
43 int main( )
44 {
45     int max,sum,flag=0;                //sum是字数组的和，max是最大的子数组的和
46     int ordern=0,orderx=0;
47     LinkList L;
48     LNode *temp,*temp1,*temp2,*head;
49     InitList(L);
50     InsertList(L);                    //由用户往链表中插入数据
51     temp=L->next;
52     max=L->next->data;                //max初值是链表中第一个数
53     for(int i=0;i<num;i++,temp=temp->next)
54     {
55         temp2=temp;
56         for(int j=0;j<num;j++,temp2=temp2->next)
57         {
58             for(int k=j;k<num;k++)
59             {
60                 sum=0;
61                 temp1=temp2;
62                 for(int h=j;h<=k;h++,temp1=temp1->next)
63                 {
64                      sum=sum+temp1->data;
65                 }
66                  if(max<sum)        //将最大值赋给max，并且保存当时的序号　
67                  {
68                      max=sum;
69                      ordern=j;
70                      orderx=k;
71                      head=temp;
72                      flag=i;        //用来求取最大值的时候的链表的情况
73                  }
74             }
75         }
76     }
77     temp=L->next;
78     cout<<"最大字数组是：";
79     for(i=0;i<(flag+ordern);i++)    //找出取得最大值的时候的子数组的第一个数
80     {
81         temp=temp->next;
82     }
83     for(int j=0;j<(orderx-ordern+1);j++,temp=temp->next)//将取得最大和的子数组元素输出
84     {
85         cout<<temp->data<<"  ";
86     }
87     cout<<endl<<"最大子数组的和是："<<max<<endl;;
88 
89     return 0;
90 }