Commit272a80f

committed

Create: 1911-maximum-alternating-subsequence-sum.cpp

1 parent78ff676 commit272a80fCopy full SHA for 272a80f

File tree

+30

-0

lines changed

+30

-0

lines changed

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+/*`
	`2`	`+Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).`
	`3`	`+The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.`
	`4`	`+For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.`
	`5`	`+`
	`6`	`+Example. Let nums = [6,2,1,2,4,5].`
	`7`	`+ The subsequence {6,1,5} can be choosen which gives maximum alternating sum of (6 + 5) - 1 = 10, which is the optimal solution in this case.`
	`8`	`+ So we return 10 as our answer.`
	`9`	`+`
	`10`	`+`
	`11`	`+`
	`12`	`+Time: O(n)`
	`13`	`+Space: O(1)`
	`14`	`+`
	`15`	`+*/`
	`16`	`+`
	`17`	`+`
	`18`	`+classSolution {`
	`19`	`+public:`
	`20`	`+longlongmaxAlternatingSum(vector<int>& nums) {`
	`21`	`+longlong even =0, odd =0, tmpEven, tmpOdd;`
	`22`	`+for(int i=nums.size()-1; i>=0; i--) {`
	`23`	`+ tmpEven =max(odd + nums[i], even);`
	`24`	`+ tmpOdd =max(even - nums[i], odd);`
	`25`	`+ even = tmpEven;`
	`26`	`+ odd = tmpOdd;`
	`27`	`+ }`
	`28`	`+return even;`
	`29`	`+ }`
	`30`	`+};`

Comments

(0)