pat 1007

output the one with the smallest indices i and j 我是真的蠢，我以为这句话叫我这种情况输出下标.....代码（=。按理说是可以优化内存的，不过我懒

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 const int inf = (1 << 31);
 6 
 7 int main(void)
 8 {
 9     int n;
10     cin >> n;
11     vector<int> v;//存数据
12     vector<int> cnt;//对应位置的最大值
13     vector<int> index;//对应位置的最大值下标
14     v.reserve(n);
15     cnt.resize(n);
16     index.resize(n);
17     for (int i = 0;i < n;i++)
18     {
19         int tmp;
20         cin >> tmp;
21         v.push_back(tmp);
22     }
23     cnt[0] = v[0];
24     index[0] = 0;
25     int max_sum = cnt[0];
26     int max_i = 0;
27     bool unique = true;
28     for (int i = 1;i < n;i++)
29     {
30         cnt[i] = v[i];
31         if (cnt[i - 1] >= 0)
32         {
33             cnt[i] += cnt[i - 1];
34             index[i] = index[i - 1];
35         }
36         else index[i] = i;
37         if (max_sum < cnt[i])
38         {
39             max_sum = cnt[i];
40             max_i = i;
41         }
42     }
43     if (max_sum < 0)
44         cout <<"0 " << v[0] << " " << v[v.size() - 1] << endl;
45     else
46     {
47         int flag = 0;
48         for (int i = 0;i < n;i++)
49             if (max_sum == cnt[i] && ++flag == 2)
50                 unique = false;
51         cout << max_sum;
52         
53         cout << " " << v[index[max_i]] << " " << v[max_i] << endl;
54     }
55     return 0;
56 }

好，来一波内存优化，参考：https://blog.csdn.net/liuchuo/article/details/52144554

这里，把t_left,i,cur看成一个当前行进的状态，并与left,right,max_s进行比较

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 const int inf = (1 << 31);
 6 
 7 int main(void)
 8 {
 9     int n;
10     cin >> n;
11     vector<int> v(n);
12     int cur = 0;
13     //int temp;
14     int max_s = inf;
15     int left = 0, right = 0;
16     int t_left = 0;
17     for (int i = 0;i < n;i++)
18     {
19         cin >> v[i];
20         cur += v[i];
21         if (cur < 0)
22         {
23             cur = 0;
24             t_left = i + 1;
25         }
26         else if (cur > max_s)
27         {
28             left = t_left;
29             max_s = cur;
30             right = i;
31         }
32     }
33     if (max_s < 0)cout << "0 " << v[0] << " " << v[n - 1];
34     else cout << max_s << " " << v[left] << " " << v[right];
35     cout << endl;
36 
37     return 0;
38 }