Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
就是求最大字数组的和还有最大子数组的开始和结束的数字
为什么我的代码在动态规划基础上改的总是不能ac呢?求解啊
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
int N;
int a[100003],aa[100001];
int begin, end;
int sum = 0, b = -1;
int f = 0;
cin >> N;
for (int i = 0; i
{
cin >> a[i]; aa[i] = a[i];
}
sort(aa, aa + N);
if (aa[N - 1] <= 0)
{
cout << sum << " " << aa[N - 1] << " " << aa[N - 1] << endl;
system("pause");
return 0;
}
for (int i = 0; i
{
if (b>=0)
{
b += a[i];
//if(!f) begin=i;
f++;
}
else b = a[i], f = 0;
if (b>sum) sum = b, begin = i - f, end = i;
}
cout << sum << " " << a[begin] << " " << a[end] << endl;
system("pause");
return 0;
}