FilesExpand file tree

 master

/

KadaneWrapArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

82 lines (76 loc) · 2.11 KB

 master

/

KadaneWrapArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

82 lines (76 loc) · 2.11 KB

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

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

package com.interview.array;

/**

* http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

* Test cases

* All negative

* All positives

* all 0s

*/

class Triplet{

int start;

int end;

int sum;

@Override

public String toString() {

return "Triplet [start=" + start + ", end=" + end + ", sum=" + sum

+ "]";

}

}

public class KadaneWrapArray {

public Triplet kadaneWrap(int arr[]){

Triplet straightKadane = kadane(arr);

int sum =0;

for(int i=0; i < arr.length; i++){

sum += arr[i];

arr[i] = -arr[i];

}

Triplet wrappedNegKadane = kadane(arr);

for(int i=0; i < arr.length; i++){

arr[i] = -arr[i];

}

if(straightKadane.sum < sum + wrappedNegKadane.sum){

straightKadane.sum = wrappedNegKadane.sum + sum;

straightKadane.start = wrappedNegKadane.end+1;

straightKadane.end = wrappedNegKadane.start-1;

}

return straightKadane;

}

/**

* This method assumes there is at least one positive number in the array.

* Otherwise it will break

* @param arr

* @return

*/

public Triplet kadane(int arr[]){

int sum =0;

int cStart = 0;

int mStart = 0;

int end = 0;

int maxSum = Integer.MIN_VALUE;

for(int i=0; i < arr.length; i++){

sum += arr[i];

if(sum <= 0){

sum = 0;

cStart = i+1;

}else{

if(sum > maxSum){

maxSum = sum;

mStart = cStart;

end = i;

}

}

}

Triplet p = new Triplet();

p.sum = maxSum;

p.start = mStart;

p.end = end;

return p;

}

public static void main(String args[]){

KadaneWrapArray kwa = new KadaneWrapArray();

int input[] = {12, -2, -6, 5, 9, -7, 3};

int input1[] = {8, -8, 9, -9, 10, -11, 12};

System.out.println(kwa.kadaneWrap(input));

System.out.println(kwa.kadaneWrap(input1));

}

}