昨天在东方海外软件研发中心碰到的一道笔试题，求解

Question

软件开发编程题算法题

Answer 1

取出list中给定的开始位置到结束位置的值 然后相加？

Answer 2

1.首先start=第一个正数的下标，end=最末一个正数的下标(此步骤可以忽略)
2.然后从start开始累加，每步累加的值都保存下来，直到end
3.在保存下来的累加值中取最大值，end=此值对应的位置
4.然后从end开始累加，每步累加的值都保存下来，直到start
5.在保存下来的累加值中取最大值，start=此值对应位置，该最大值即为max
over
原理：
你想想，如果A[x]+...+A[x+m]>A[x]+...+A[x+n]
是否可以推出A[y]+...+A[y+m]>A[y]+...+A[y+n]呢？
所以，我们得出结论，对于连续累加，无论start为多少(定值)，产生最大sum的end是某个固定位置
反之，无论end为多少(定值)，产生最大sum的start为固定位置
这样，就变成了两个独立的“寻找位置”的任务了对于上题，正向扫描为2 → 1 → 5 → 2 → 4，最大值在第3位，end=2
反向扫描为4 ← 2 ← 3 ← -1 ← 2，最大值在第1位，start=0
注：如果你扫描过程中发现多个最大值，说明他们都是可以的，例如-1，1，2，1，-1
这种情况下为了节省扫描次数，选用最小的end和最大的start

Answer 3

抱歉，有一段话写错了，这里更正如下
============================
你想想，如果A[x]+...+A[m]>A[x]+...+A[n]
是否可以推出A[y]+...+A[m]>A[y]+...+A[n]呢？

Answer 4

算是动态规划的一个经典题目吧：http://wenku.baidu.com/view/b1a18d114431b90d6c85c7be.html

Answer 5

不就是一个for循环吗？ 
int sum = 0; // 其他还需要判断传的begin与end数值的合法性，比如正负数，是否超过数组大小等等。
for(int i=begin;i<=end;i++){
  sum + = A[i];
}

Answer 6

    public static void main(String[] args)
    {
        //初始化
        List<Integer> list = Arrays.asList(new Integer[] {2, -1, 4, -3, 2});
        System.out.println(list);
        
        //辅助变量：当前起始下标，最大值的起始下标，最大值的结尾下标，当前求和，最大求和
        int start, maxStart, maxEnd, sum, maxSum;
        start = maxStart = maxEnd = sum = maxSum = 0;
        //标记上一个值是否为负数
        boolean isFirst = false;
        
        for (int i = 0; i < list.size(); i++)
        {
            //当前求和
            sum += list.get(i);
            
            //若小于0，跳过本次循环
            if (sum < 0)
            {
                //当前和清零
                sum = 0;
                //上一个值为负数
                isFirst = true;
                continue;
            }
            else
            {
                //上一个值为负数，则起始下标取当前值
                if(isFirst)
                {
                    start = i;
                    isFirst = false;
                }
                
                //若当前求和大于最大求和，记录最大和以及起始、结尾下标
                if (sum > maxSum)
                {
                    maxSum = sum;
                    maxStart = start;
                    maxEnd = i;
                }
            }
        }
        System.out.println("最大值之和："+maxSum);
        System.out.println("起始下标："+maxStart);
        System.out.println("终止下标："+maxEnd);
    }

Answer 7

这不是CSDN编程挑战赛的一个题目吗？
int MaxSum(int* a,int n)
{
    int hasresult = 0;
    int max=0;
    int sum=0;
    int i;
    for(i=0; i<n; i++) {
        sum += a[i];
        if(!hasresult || sum>max) {
            hasresult = 1;        
            max = sum;
        }
        if(sum<0)
            sum = 0;
    }
    return max;
}