codekofi
← All questions

Maximum Subarray

HardGreedy

The problem

Given an integer array, return the largest sum obtainable from a contiguous non-empty subarray.

maxSubArray({-2, 1, -3, 4, -1, 2, 1, -5, 4})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int maxSubArray(const vector<int>& nums) {
2
3 int n = nums.size();
4 int running = nums[0];
5 int ans = nums[0];
6
7 for (int i = 1; i <= n; i++) {
8
9 if (running < 0) {
10 running = 0;
11 }
12
13 running = running + nums[i - 1];
14
15 if (running > ans) {
16 ans = running;
17 }
18 }
19
20 return ans;
21}
1int maxSubArray(const vector<int>& nums) {
2
3 int n = nums.size();
4 int running = nums[0];
5 int ans = nums[0];
6
7 for (int i = 0; i < n; i++) {
8
9 if (!(running < 0)) {
10 running = 0;
11 }
12
13 running = running + nums[i];
14
15 if (running > ans) {
16 ans = running;
17 }
18 }
19
20 return ans;
21}
1int maxSubArray(const vector<int>& nums) {
2
3 int n = nums.size();
4 int running = nums[0];
5 int ans = nums[0];
6
7 for (int i = 1; i < n; i++) {
8
9 if (running < 0) {
10 running = 0;
11 }
12
13 running = running + nums[i];
14
15 if (running > ans) {
16 ans = running;
17 }
18 }
19
20 return ans;
21}