C++

Forum

 
Array exercise

frek (576)
The exercise says:

A non-empty array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].
For example, array A such that:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
contains the following example double slices:

double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.

Write a function:
int solution(vector<int> &A);
that, given a non-empty array A consisting of N integers, returns the maximal sum of any double slice.
For example, given:

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
the function should return 17, because no double slice of array A has a sum of greater than 17.

Write an efficient algorithm for the following assumptions:
N is an integer within the range [3..100,000];
each element of array A is an integer within the range [−10,000..10,000].

My code works fine with the following test cases but still don't get the expected score! I'm not sure that I've not understood the exercise description or my code sucks!
PS: I don't need code, only hints! 

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
 
int solution(std::vector<int>& A) {
	if (A.size() < 3) return 0;
	bool all_positive{ true };

	for (size_t i = 1; i < A.size() - 1; ++i)
		if (A[i] < 0) all_positive = false; // Some element(s) inside the range 
	                                       // [1, size -2] is/are not posititve
	if (all_positive) {
		int min_element = *std::min_element(A.begin() + 1, A.end() - 1);
		size_t max_triple{ 0 };

		for (int a : A)
			max_triple += a;

		return max_triple - A[0] - min_element - A[A.size() - 1];
	}

	int first_side_max{ 0 }, second_side_max{ 0 }, temp{ A[1] };

	for (size_t i = 2; i < A.size() - 1; ++i)
		if (temp < 0 && A[i] >= 0)
			temp = A[i];
		else if (temp + A[i] >= temp)
			temp += A[i];
		else if (temp > std::min(first_side_max, second_side_max)) {
			(first_side_max < second_side_max ? first_side_max : second_side_max) = temp;
			temp = 0;
		}
		else if (++i < A.size() - 1) temp = A[i];

	if (temp > std::min(first_side_max, second_side_max))  // catch 'temp' remained in the loop
		(first_side_max < second_side_max ? first_side_max : second_side_max) = temp;

	return first_side_max + second_side_max;
}

int main()
{
	std::vector<std::vector<int>> vec {
		{-2, 1, 1, 3, 4, 8, 7},            // 16
		{3, 5, 6, -3, 7, 1, 4, 2},         // 23
		{3, 2, 6, -1, 4, 5, -1, 2},        // 17
	    {5, 17, 0, 3},                     // 17
		{-2, -3, -4, 1, -5, -6, -7},       // 1
		{ -2, -3, -5, -1, -4, -8, -6},     // 0
		{ 4, 5, 1, -3, 2, 1},              // 8
		{-3, -5, 2, 3, 4, 5},              // 9
	    {1, 2, 3, 4, 5, 6}                 // 12
 	};

	for (auto& v : vec)
		std::cout << solution(v) << '\n';
}

Last edited on
lastchance (6980)
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
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution( const vector<int> &A )
{
   int N = A.size();
   vector<int> left( N, 0 ), right( N, 0 );
   for ( int Y = 2; Y <= N - 2; Y++ ) left [Y] = max( left [Y-1] + A[Y-1], 0 );
   for ( int Y = N - 3; Y >= 1; Y-- ) right[Y] = max( right[Y+1] + A[Y+1], 0 );
   int best = 0;
   for ( int Y = 1; Y <= N - 2; Y++ )
   {
      int test = left[Y] + right[Y];
      if ( test > best ) best = test;
   }
   return best;
}

int main()
{
   vector< vector<int> > tests = {
                {-2, 1, 1, 3, 4, 8, 7},            // 16
                {3, 5, 6, -3, 7, 1, 4, 2},         // 23
                {3, 2, 6, -1, 4, 5, -1, 2},        // 17
                {5, 17, 0, 3},                     // 17
                {-2, -3, -4, 1, -5, -6, -7},       // 1
                { -2, -3, -5, -1, -4, -8, -6},     // 0
                { 4, 5, 1, -3, 2, 1},              // 8
                {-3, -5, 2, 3, 4, 5},              // 9
                {1, 2, 3, 4, 5, 6}                 // 12
                                 };
   for ( auto &V : tests ) cout << solution( V ) << '\n';
}

kbw (9488)
@lastchance: PS: I don't need code, only hints!
lastchance (6980)
Yeah, but I couldn't work out what your code was doing ... so it's impossible to comment on your approach.

Maybe you try to explain carefully in words what you are trying to do: it's often easier than slightly messy code.
frek (576)
My code works fine with the following test cases but the problem is that I don't know what different test case I use against it to see the problem! :|

{-5, -4, -6, -2, -1, -4, -12},       // 0
{1, -3, -4, -12, -1, -2},            // 0
{-2, 4, -2, -3, -9, -5},             // 4
{1, -2, 3, 4, -5, 7, 6, -4, 3},      // 20
{9, 2, 3, -5, 3, 2, 6},              // 10
{3, -4, 5, -6, 7, -8, 4},            // 12
{5, -4, -5, -6, 9},                  // 0
{1, 2, 3, 4, 5, 6}                   // 12
lastchance (6980)
OK, try the following vector:
{ -19, 16, -19, -6, 8, -2, 3, -4, 1, 6 }

I think (and my code produces) the answer 19. (X, 16, Y, -6, 8, -2, 3, Z) ==> 16+3=19
Your code produces 24.


I'll see if I can find any discrepancies with shorter vectors!



OK: try { -3, 11, -11, -3, 19, 3 }
I think the answer is 27 (from 11 + (-3+19) ).
Your code produces 30.
Last edited on
frek (576)
yes, my code works differently. I just got the exact point of the exercise so should redesign my code.
lastchance (6980)
@frek,
The easiest way to generate tests for your algorithm in this instance is:
(1) Generate random vectors (just fix their length and the limits of each element).
(2) Write a separate function that will check those vectors by brute force. (In this instance it will be O(N4) - separate loops for X, Y, Z and the summation - but it will be fine for relatively small N and allow you to test your algorithm.)

People knock brute-force algorithms because they have hopeless asymptotic order, but they are simple and much less error-prone and, outside of competitive programming and population-size statistics they will get you a quick answer for moderate N. At the very least, they will allow you to check more complex algorithms.
Last edited on
Topic archived. No new replies allowed.