JAVA算法:求最大连续上升子数组的和(详细求解)
给定含有 n 个正的非重复整数的整型数组。
问题是找出满足条件为连续增加(上升)的子数组的最大和。
解释:什么是连续上升的子数组呢?就是子数组的元素按升序排列。
问题分析
伪代码如下:
Let arr be the array of size n
Let result be the required sumint largestSum(arr, n) result = INT_MIN // Initialize resulti = 0while i < n// Find sum of longest increasing subarray// starting with icurr_sum = arr[i];while i+1 < n && arr[i] < arr[i+1]curr_sum += arr[i+1];i++; // If current sum is greater than current// result.if result < curr_sumresult = curr_sum; i++;
return result
算法设计
package com.bean.algorithm.basic;public class LargestSumContiguousIncreasingSubarray