Skip to main content
Code Review

Return to Answer

added 9 characters in body
Source Link
G. Sliepen
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
using namespace std;
...
int window = std::accumulate(std::begin(data), std::end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = std::accumulate(std::begin(data), std::begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = std::max(maxOnes, onesInWindow);  
}

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
using namespace std;
...
int window = accumulate(begin(data), end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = accumulate(begin(data), begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = max(maxOnes, onesInWindow);  
}

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
...
int window = std::accumulate(std::begin(data), std::end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = std::accumulate(std::begin(data), std::begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = std::max(maxOnes, onesInWindow);  
}
added 61 characters in body
Source Link
G. Sliepen
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
using namespace std;
...
int window = accumulate(begin(data), end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = accumulate(begin(data), begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = max(maxOnes, onesInWindow);  
}

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

int window = accumulate(begin(data), end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = accumulate(begin(data), begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = max(maxOnes, onesInWindow);  
}

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
using namespace std;
...
int window = accumulate(begin(data), end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = accumulate(begin(data), begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = max(maxOnes, onesInWindow);  
}
Source Link
G. Sliepen
G. Sliepen
  • 69.5k
  • 3
  • 75
  • 180

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

int window = accumulate(begin(data), end(data), 0);

You don't need onesTillNow

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = accumulate(begin(data), begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = max(maxOnes, onesInWindow);  
}