Array Partitioning
Feb 9, 2015 at 10:15pm UTC
I need to write a program which for a given array of integers determines whether or not it can be partitioned into two subarrays, each of which is in strictly increasing order.
When i run test cases my program passes 4/5 and I cant find the error for the last case. (I dont not know the values of the test case).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
#include<iostream>
#include<string>
using namespace std;
bool run(){
int numbers;
int *arr;
cin >> numbers;
arr = new int [numbers];
for (int i = 0; i < numbers; i++)
cin >> arr[i];
long long int MAX = 0;
long long int MAX2 = 0;
string stra = "" ;
string strb = "" ;
string result = "" ;
string total = "" ;
long long int sum = 0;
for (int i = 0; i < numbers; i++){
if (arr[i] >= MAX && arr[i] != arr[i - 1]){
stra += to_string(arr[i]);
MAX = arr[i];
}
else
if (arr[i] >= MAX2 && MAX2 != MAX){
strb += to_string(arr[i]);
MAX2 = arr[i];
}
}
for (int i = 0; i < numbers; i++){
result = to_string(arr[i]);
total += result;
}
long long int len1 = stra.length();
long long int len2 = strb.length();
sum += len1 + len2;
delete [] arr;
if (sum != total.length())
return false ;
else
return true ;
}
int main()
{
int test;
cin >> test;
while (test > 0)
{
if (run())
cout << "Yes\n" ;
else
cout << "No\n" ;
test--;
}
system("pause" );
}
Last edited on Feb 9, 2015 at 10:15pm UTC
Topic archived. No new replies allowed.