happycoding/MaxSliceSum.cpp at master · hellocomrade/happycoding · GitHub

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
//https://codility.com/programmers/task/max_slice_sum
#include <cassert>
#include <limits>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

//classic max sub array
int solutionMaxSliceSum1(const vector<int> &A) {
    int len = A.size();
    assert(len > 0);
    //integer overflow is possible, long long is the safe choice since it's guaranteed to be 8 bytes
    //long, however, could still be 4 bytes on Windows even it's x64
	long long maxhere = 0, maxsofar = numeric_limits<long long>::min(), tmp;
    for (int i : A)
    {
	tmp = maxhere + i;
	//update maxsofar first and then maxhere to make sure negative max value can be stored properly
	maxsofar = std::max(maxsofar, tmp);
	maxhere = std::max(0ll, tmp);
    }
    return static_cast<int>(maxsofar);
}
int solutionMaxSliceSum(const vector<int> &A) {
	int len = A.size();
	assert(len > 0);
	long long maxhere = 0, maxsofar = numeric_limits<long long>::min();
	for (int i : A)
	{
		maxhere = std::max((long long)i, maxhere + (long long)i);
		maxsofar = std::max(maxsofar, maxhere);
	}
	return static_cast<int>(maxsofar);
}
void testMaxSliceSum()
{
	cout << "Expect 5: " << solutionMaxSliceSum(vector<int>({ 3, 2, -6, 4, 0 })) << endl;
	cout << "Expect 6: " << solutionMaxSliceSum(vector<int>({ 0, 1, 2, 3, -5, -8 })) << endl;
	cout << "Expect 0: " << solutionMaxSliceSum(vector<int>({ 0 })) << endl;
	cout << "Expect -1: " << solutionMaxSliceSum(vector<int>({ -1 })) << endl;
	cout << "Expect 1: " << solutionMaxSliceSum(vector<int>({ 1 })) << endl;
	cout << "Expect 25: " << solutionMaxSliceSum(vector<int>({ 8, 7, -3, 6, -2, 9 })) << endl;
	cout << "Expect -1: " << solutionMaxSliceSum(vector<int>({ -3, -1, -3, -6, -2, -9 })) << endl;
	cout << "Expect -1: " << solutionMaxSliceSum(vector<int>({ -1, -1, -3, -6, -2, -9 })) << endl;
	cout << "Expect 0: " << solutionMaxSliceSum(vector<int>({ -1, -1, -3, 0, -6, -2, -9 })) << endl;
	cout << "Expect 0: " << solutionMaxSliceSum(vector<int>({ 0, -1, 0, 0, -6, -2, -9 })) << endl;
	cout << "Expect 1: " << solutionMaxSliceSum(vector<int>({ 0, -1, 0, 1, -6, -2, -9 })) << endl;
}