FilesExpand file tree

 main

/

crumbs22.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (32 loc) · 632 Bytes

 main

/

crumbs22.cpp

Top

File metadata and controls

• Code
• Blame

38 lines (32 loc) · 632 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

/*

TC: O(n)

SC: O(1)

풀이 방법:

- sum에 현재 값을 더해가면서 최대값을 갱신한다

- 누적합이 음수가 됐을 때 0으로 리셋한다

고민했던 케이스(left와 right 포인터를 두고 풀었을 때):

[-2, -1]

[-1, -2]

[-2, 1]

[-1, 1, 2, 1]

*/

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int max = nums[0];

int sum = 0;

for (int i = 0; i < nums.size(); i++)

{

sum += nums[i];

if (sum > max)

max = sum;

if (sum < 0)

sum = 0;

}

return (max);

}

};